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

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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