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  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
LibraryThing Review
User Review  dpf  LibraryThingA strong text, but quite formal. Not the most readable. Read full review
Contents
Preliminaries  1 
Finite Automata and Regular Expressions  13 
Properties of Regular Sets  55 
Copyright  
13 other sections not shown
Other editions  View all
Common terms and phrases
2DFA algorithm alphabet automata binary cells CFL's class of languages closure properties computation construct contains contextfree grammars contextfree languages crossing sequences CSL's DCFL DCFL's defined denote deterministic DPDA DSPACE(log empty encoding equivalent Example Exercise finite automaton finite control finite number follows full trio Ginsburg given graph Greibach halts Hamilton circuit homomorphism ID's inductive hypothesis infinite input symbol integers labeled language accepted leftmost length Let G linear logspace logspace reduction Moore machine moves nondeterministic Note NPcomplete oracle output pair path polynomial problem productions Proof Let prove PSPACE pumping lemma pushdown automaton r.e. sets recursive function recursive language reduce regular expression regular set rightmost derivation scanned sentential form shown in Fig simulate stack symbol storage tape string subset Suppose tape head tape symbol terminal Theorem TM's transition Turing machine undecidable variables vertex vertices viable prefix word