An Introduction to Formal Languages and AutomataFormal languages, automata, computability, and related matters form the major part of the theory of computation. This textbook is designed for an introductory course for computer science and computer engineering majors who have knowledge of some higher-level programming language, the fundamentals of |
Contents
Introduction to the Theory of Computation | 1 |
Graphs and Trees | 7 |
Automata | 25 |
Copyright | |
16 other sections not shown
Other editions - View all
Common terms and phrases
A-productions accepts the language argument Chomsky normal form computation configuration Consider construction context-free grammar context-sensitive grammar context-sensitive languages control unit countable defined definition denoted derivation tree deterministic context-free language equivalent Example Exercise exists family of context-free finite number G₁ Give given grammar G Greibach normal form halting problem induction instantaneous description integers L₁ L1 and L2 labeled language accepted language families languages is closed leftmost linear bounded automaton M₁ move nondeterminism nondeterministic npda number of a's parsing primitive recursive productions programming languages proof pumping lemma pushdown automata q₁ read-write head recursively enumerable languages regular expression regular languages result s-grammar S₁ sentential form sequence Show shown in Figure simulation solution stack standard Turing machine step subset tape terminal Theorem transition function transition graph Turing's thesis unit-productions unrestricted grammar V₁ variable vertex w₁