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
2DFA A₁ a₂ algorithm alphabet automata binary cells CFL's class of languages closure properties construct contains context-free grammars context-free languages crossing sequences DCFL defined denote deterministic DPDA empty equivalent Example Exercise finite automaton finite control finite number follows G₁ G₂ graph halts homomorphism ID's inductive hypothesis infinite input symbol integers L₁ L₂ labeled languages accepted leftmost length linear log-space log-space reductions M₁ M₂ Mealy machine Moore machine moves MPCP nondeterministic Note NP-complete oracle output P₁ pair prefix problem productions Proof Let prove PSPACE pumping lemma pushdown automaton q₁ r.e. sets r₁ recursive functions regular expression regular set S₁ scanned sentential form shown in Fig simulate stack symbol storage tape string Suppose tape head tape symbol terminal Theorem TM's Turing machine undecidable v₁ variable vertex viable prefix w₁ word x₁