A generator of context-sensitive languages

摘要

The existence of a context-sensitive grammar, Gu, which acts as a “generator” of all context-sensitive languages is established. Specifically, Gu has the property that for each context-sensitive language, L, there exists a regular set, RL, and an e-limited gsm, gL, such that L=gL(L(Gu)∩RL). It follows that the family of context-sensitive languages is a principal AFL. An analogous result is proved for deterministic contextsensitive languages.