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?


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.

| cite | improve this answer | |
  • $\begingroup$ Appreciate the answer. Do you know if there's a book or article or something similar that has this proven? $\endgroup$ – John Doe the Righteous Sep 3 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.