Question

The original formulation of the 3 restricted grammar types of Chomsky all included the restriction that the right-hand side of a replacement cannot be $\epsilon$ (non-contracting). This, however, can be (and usually is) lifted for regular and context-free grammars (i.e. they are allowed to have productions of the form $X \to \epsilon$) without altering the class of languages generated.

The rule, however, remains for context-sensitive grammars.

My question is, given a grammar with productions $\alpha X \beta \to \alpha \xi \beta$ where $\alpha, \beta, \xi\in (N \cup T)^*$ (i.e. a context-sensitive grammar with $\epsilon$-rules), what class of languages does that describe? The recursively enumerable ones (same as unrestricted grammars) or something else?

Was it helpful?

Solution

It can be shown that the context sensitive grammars you describe are equivalent to just asking for productions $\alpha \to \beta$ with $\lvert \alpha \rvert \le \lvert \beta \rvert$. So allowing productions $A \to \varepsilon$ just removes the restriction on lengths, and you have landed on unrestricted grammars.

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top