Introduction to Automata Theory, Languages, and ComputationAddison-Wesley, 1979 - 418 pages Preliminaries. 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. |
Table des matières
portance First has been the use of languagetheory concepts such as nondeterminism | 1 |
USE OF THE BOOK | 8 |
Chapter | 10 |
Droits d'auteur | |
24 autres sections non affichées
Autres éditions - Tout afficher
Introduction to Automata Theory, Languages, and Computation John E. Hopcroft,Jeffrey D. Ullman Affichage d'extraits - 1979 |
Introduction to Automata Theory, Languages, and Computation John E. Hopcroft,Jeffrey D. Ullman Affichage d'extraits - 1979 |
Expressions et termes fréquents
a₁ accepts algorithm alphabet appears applied assume automata begin called cells CFL's closed closure complexity computation Consider consists construct contains context-free corresponding crossing defined denoted derivation determine deterministic empty enters equivalent Example Exercise exists final finite automaton follows formal function give given grammar graph halts head induction infinite initial input input symbol integers L₁ L₂ labeled language Lemma length M₁ M₂ moves nondeterministic Note operators output pair path position problem productions Proof properties prove q₁ recursive reduces regular expression regular set relation replaced represented result rule satisfies scanned sequence simulate solution space stack steps string Suppose symbol takes tape terminal Theorem transition tree true Turing machine undecidable valid variable vertex vertices