Introduction to Automata Theory, Languages, and ComputationPreliminaries. Finite automata and regular expressions. Properties of regular sets. Context-free grammars. Pushdown automata; Properties of context-free languages. Turing machines. Undecidability. The Cohmsky hierarchy. Heterministic context-free languages. Closure properties of families of languages. Computational complexity theory. Intractable problems. Highlights of other important language classes. |
Other editions - View all
Common terms and phrases
a₁ a₂ algorithm alphabet automata binary cells CFL's class of languages closure properties complexity computation construct contains context-free grammars context-free languages crossing sequences DCFL DCFL's defined denote deterministic DPDA E₁ empty equivalent Example Exercise finite automaton finite control finite number follows G₁ graph Greibach halts Hamilton circuit homomorphism ID's infinite input symbol integers L₁ L₂ languages accepted leftmost length linear log-space log-space reductions M₁ M₂ Mealy machine Moore machine moves nondeterministic NP-complete oracle output P₁ pair polynomial problem productions Proof Let prove PSPACE pumping lemma pushdown automaton q₁ recursive function reduce regular expression regular set scanned sentential form shown in Fig simulate space stack symbol storage tape string Suppose tape head tape symbol terminal Theorem TM's transition Turing machine undecidable v₁ variables vertex vertices viable prefix w₁ X₁