Introduction to Automata Theory, Languages, and ComputationPreliminaries. Finite automata and regular expressions. Properties of regular sets. Contextfree grammars. Pushdown automata; Properties of contextfree languages. Turing machines. Undecidability. The Cohmsky hierarchy. Heterministic contextfree languages. Closure properties of families of languages. Computational complexity theory. Intractable problems. Highlights of other important language classes. 
What people are saying  Write a review
User ratings
5 stars 
 
4 stars 
 
3 stars 
 
2 stars 
 
1 star 

LibraryThing Review
User Review  Foretopman  LibraryThingI need to make it clear right at the beginning that this is a review of the first (1979) edition of this book. It's my understanding that the second edition is better. I knew that this book was going ... Read full review
LibraryThing Review
User Review  dominus  LibraryThing(This is a review of the first edition of this book.) This is another one of those rotten books that is difficult to read even when you already know the subject matter backward and forward. One of the ... Read full review
Other editions  View all
Common terms and phrases
accepted algorithm alphabet appears applied assume automata begin bounded called cells CFL's circuit closed closure complexity computation Consider consists constant construct contains contextfree corresponding defined denote derivation determine deterministic empty enters equivalent Example Exercise exists fact final finite finite automaton follows formal function give given grammar graph halts head homomorphism induction infinite initial input input symbol integers labeled language least Lemma length moves nondeterministic Note operations output pair path position prefix problem productions Proof properties prove recursive reduce regular expression regular set relation replaced represented result rule satisfies scanned sequence shown simulate solution space stack steps storage string Suppose symbol takes tape terminal Theorem track transition tree true Turing machine undecidable valid variables vertex vertices