The Mathematical Theory of Context Free Languages |
Contents
CONTEXTFREE AND ALGOLLIKE LANGUAGES | 6 |
ACCEPTORS AND LANGUAGES | 46 |
DECIDABILITY | 115 |
Copyright | |
5 other sections not shown
Other editions - View all
Common terms and phrases
A₁ arbitrary language bounded languages complete the proof context-free grammar context-free languages context-sensitive language defined determine for arbitrary deterministic pda disjoint linear sets distinct symbols e-free Example Let Exercise exists a gsm finite number finite set finite union function G is unambiguous G₁ grammar G gsm mapping gsm which maps Hence homomorphism induction initial subword integer L₁ and L2 L₂ leftmost derivation Lemma Let G linearly independent periods M₁ minimal n-tuple node name non-e words Null(M occurrence P₁ production programming languages PROOF Let prove pushdown transducer recursively solvable recursively unsolvable regular set right-linear semilinear set sequence sequential transducer solvable to determine stratified and linearly suffices to show Suppose T₁ Theorem tree union of linear union of sets unsolvable to determine variable w₁ w₂ Wi+1 ξη ξι