Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
