Introduction to Formal Languages, Automata Theory and ComputationIntroduction to Formal Languages, Automata Theory and Computation presents the theoretical concepts in a concise and clear manner, with an in-depth coverage of formal grammar and basic automata types. The book also examines the underlying theory and principles of computation and is highly suitable to the undergraduate courses in computer science and information technology. An overview of the recent trends in the field and applications are introduced at the appropriate places to stimulate the interest of active learners. |
Contents
Preliminaries | 1 |
Grammars | 19 |
Finite State Automata | 57 |
Characterization | 87 |
Finite State Automata with Output | 97 |
Variants of Finite Automata | 111 |
Pushdown Automata | 145 |
ContextFree GrammarsProperties | 165 |
Turing Machines | 193 |
Variations of Turing Machines | 227 |
Universal Turing Machine | 247 |
Time and Space Complexity | 277 |
Recent Trends and Applications | 307 |
New Models of Computation | 357 |
Common terms and phrases
a₁ algorithm alphabet applied automata automaton binary cell CFG G Chomsky normal form closure component computation construct contains q context-free contextual grammar corresponding crossing sequences defined as follows Definition denoted derivation tree deterministic DFSA empty Example family of languages Figure finite set finite state automaton function given grammar G graph halting problem halts Hence homomorphism induction initial input tape integer k-mode L-systems L₁ L₂ language accepted leftmost length Let G linear mapping Mealy machine membrane mode multiset NFSA node non-deterministic non-terminal NP-complete number of a's output P₁ P₂ problem Proof Let prove pumping lemma pushdown q₁ q₂ R₁ recursively enumerable regular expression regular languages regular set represented rules S₁ set of strings simulate Solution splicing stack steps subset symbol tape head Theorem transition Turing machines undecidable variables w₁ X₁