The Mathematical Theory of Context Free Languages |
Other editions - View all
Common terms and phrases
arbitrary language bounded languages complete the proof context-free grammar context-free languages context-sensitive language defined determine for arbitrary deterministic language deterministic pda disjoint linear sets distinct symbols Exercise exists a gsm finite number finite set finite union function G₁ grammar G gsm mapping gsm which maps Hence homomorphism induction inherently ambiguous languages initial subword integer L₁ L₂ leftmost derivation Lemma Let G linear grammar linearly independent periods M₁ minimal n-tuple node name non-e words nonlanguage Null(M occurrence p₁ positive solution production programming languages PROOF Let prove pushdown transducer recursively solvable recursively unsolvable regular sets right-linear semilinear set sequence sequential transducer solvable to determine stratified and linearly suffices to show Suppose T₁ Theorem tree u₁ union of linear unsolvable to determine variable w₁ w₂ Wi+1 ξη ξι