I've had a few similar courses at university, but they've always been limited to NP-completeness, does anyone know how I can expand on this? That is, learn beyond NP-completeness (Books / Online courses etc)?
A Course on Automata Theory
21–30 of 34 posts
Re: A Course on Automata Theory
#22I've had a few similar courses at university, but they've always been limited to NP-completeness, does anyone know how I can expand on this? That is, learn beyond NP-completeness (Books / Online courses etc)?
If you're interested in computational complexity theory, I recommend "Computational Complexity" by Christos Papadimitriou. It's a classic, though it's a bit dated.
Re: A Course on Automata Theory
#23For those who want to dive further in automata theory, transducers and the non-commutative algebraic view of the theory, the following one by J. Sakarovitch is a fantastic book : http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=978...
Re: A Course on Automata Theory
#24When I was an undergrad at Université de Montréal, the theory of computation class which dealt with automata was called "Informatique Théorique"; literally, "theoretical computer science". "Why do theoretical computer science," I'd ask, "let's do practical computer science instead!" However, thanks to the enthusiasm of my professor and his teaching assistant and the very interesting nature of the subject, it became t…
Regular expressions are probably one of the most practical and immediately obviously useful things to come out of automata theory.
I'm interested to hear you say this. I teach this course, to students who mostly go on to do Java coding. I have several times run into an old student who told me that they never once used regexes after my class, either in school or in work.
Re: A Course on Automata Theory
#25Earlier quoted context omitted.
Regular expressions are probably one of the most practical and immediately obviously useful things to come out of automata theory.
I'm interested to hear you say this. I teach this course, to students who mostly go on to do Java coding. I have several times run into an old student who told me that they never once used regexes after my class, either in school or in work.
That is very surprising to hear. Regular expressions are used all over the place! I wouldn't want to work with a person who does not have at least the basic workings of Regex down pat.
Re: A Course on Automata Theory
#26Earlier quoted context omitted.
Regular expressions are probably one of the most practical and immediately obviously useful things to come out of automata theory.
I'm interested to hear you say this. I teach this course, to students who mostly go on to do Java coding. I have several times run into an old student who told me that they never once used regexes after my class, either in school or in work.
One reason may be that practical regexes have so many extensions that you can't many of the usual tricks on them.
http://stackoverflow.com/questions/6363397/how-to-tell-if-on...
Re: A Course on Automata Theory
#27I am an EE who has previously tried to take this course and found it incredibly hard because of theory, formal proofs etc.. Can anyone recommend a book, lecture notes to accompany this course to make life easy?
[deleted]
Re: A Course on Automata Theory
#28Earlier quoted context omitted.
Regular expressions are probably one of the most practical and immediately obviously useful things to come out of automata theory.
I'm interested to hear you say this. I teach this course, to students who mostly go on to do Java coding. I have several times run into an old student who told me that they never once used regexes after my class, either in school or in work.
I'm surprised - Did you ask them how do they search for patterns? Entries in log files, function definitions or usage in code, matching files in a shell?
Re: A Course on Automata Theory
#29When I was an undergrad at Université de Montréal, the theory of computation class which dealt with automata was called "Informatique Théorique"; literally, "theoretical computer science". "Why do theoretical computer science," I'd ask, "let's do practical computer science instead!" However, thanks to the enthusiasm of my professor and his teaching assistant and the very interesting nature of the subject, it became t…
Regular expressions are probably one of the most practical and immediately obviously useful things to come out of automata theory.
I already knew Perl and Posix regex when I took automata. I cruised through the initial basics of regular expressions faster than my peers. But I got into trouble after I learned that regex contains a bunch of features (hacks) that have no grounding in pure automata theory. I had to unlearn a whole bunch of things.
Re: A Course on Automata Theory
#30I was lucky to have an excellent professor for a similar course in college (it was called Computation Theory). It completely changed the way I think about programming. Specifically, it changed how I think about program state and software bugs. Also, knowing about finite state machines really helps with requirement analysis.
So, highly recommended.