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