Introduction to Formal LanguagesAccessible introduction to mainstream formal language theory: operations on languages, context-sensitive languages, automata, syntax analysis, derivation languages, much more. Worked examples. Exercises. |
Contents
Operations on Languages | 9 |
ContextFree Languages | 17 |
12 | 36 |
Copyright | |
8 other sections not shown
Other editions - View all
Common terms and phrases
accepted algorithm alphabet applied arbitrary assume automata automaton called cell Chapter completes the proof computation configuration Consider construction contains context-free grammar context-free language context-sensitive Corollary corresponding decidable defined Definition denoted derivation derivation tree derivation word deterministic empty enumerable equivalent Example fact Figure finite finite automaton function further give given grammar G graph head Hence holds implies induction initial input word introduced L₂ language leftmost length letters mapping means moves Namely node nondeterministic nonterminal normal form Note occur operations P₁ possible problem procedure production proof properties prove pushdown automaton recursive reduction relation replaced represented result rewriting rules rules in F sequence shown side simulated stack step string symbol tape terminal Theorem theory Turing machine variables W₁ W₂