Context-sensitive
Languages
Theorem: For every CSG G, there is an LBA M such that L(G) = L(M).
Proof: See page 732 in [Meduna:
Automata and Languages]
Conclusion: The fundamental models for
context-sensitive languages are
1) Context-sensitive grammars
2)
Linear bounded automata
Definition: Let L be a language.
L is a context-sensitive if there exists a
context-sensitive
grammar G that L
= L(G).
Theorem: For every LBA M, there is an CSG G such that L(M) = L(G).
Proof: See page 734 in [Meduna:
Automata and Languages]
33/45