5
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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 ... $\endgroup$ – Ewan Delanoy Feb 17 at 7:23

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.