# Mildly context-sensitive grammar

Consider a context-sensitive grammar $$G$$, such that all the productions of $$G$$ have the form $$A\to \alpha$$ or $$Ab \to \alpha b$$ (in other words, the left context is always empty and the right context is either empty or consists of just one terminal).

Is the language defined by such a grammar necessarily context-free ?

In all the toy examples I considered, the original context-sensitive grammar can be enlarged into an equivalent context-free one.

• Penttonen normal form has productions $A \to a$, $A \to BC$, and $AB \to AC$. Your productions are however less powerful. Feb 16, 2019 at 18:46
• Theorem 1 here seems to imply that your grammars generate context-free languages. Feb 16, 2019 at 18:47

You could have written a paper bases on your discovery had you been living many years ago.

In fact, the paper Terminal Context in Context-Sensitive Grammars by Ronald V. Book, 1972 mentioned by Yuval proved the following theorem, edited slightly for the sake of current question.

Theorem 3. If $$G$$ is a context-sensitive grammar with terminals $$\Sigma$$, non-terminals $$N$$ such that every non-context-free rule is of the form $$\alpha Z\beta \to \alpha\gamma \beta$$ where $$\alpha\in\Sigma^*$$, $$\beta\in\Sigma^*$$ and $$Z\in N$$, then $$L(G)$$ is context-free.

The grammar in the theorem above is much more general than the grammar described in the question. In fact, if we restrict $$\alpha$$ to be empty and $$\beta\in\Sigma$$, we obtain the grammar described in the question.

You can check that article for a proof of the theorem as well as more insight into how to force context-sensitive grammars to be context-free. (You could probably write a paper if you solve the conjecture at the end of that paper.)

Here is one exercise that is within easy reach.

Exercise 1. If $$G$$ is a context-free grammar except one rule, which is of form $$Aa\to Ba$$, where $$a$$ is a terminal and $$A$$ and $$B$$ are two non-terminals, then $$L(G)$$ is context-free.

• Thanks for your feedback. Unfortunately I am away from home at the moment and it'll be several weeks before I can access that article. Meanwhile I'll have a go at the exercise ... Feb 17, 2019 at 7:23