# 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. Commented Feb 16, 2019 at 18:46
• Theorem 1 here seems to imply that your grammars generate context-free languages. Commented Feb 16, 2019 at 18:47

You could have written a paper based on your discovery had you been researching this problem 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 2. 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 question is the special case of the grammar in the theorem above where $$\alpha$$ is the empty string and $$\beta$$ is either the empty string or a terminal.

Check that paper for a proof of the theorem as well as more insight on how to force context-sensitive grammars to be context-free. (You can probably publish a paper if you could 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.