patternMinor
Mildly context-sensitive grammar
Viewed 0 times
contextsensitivegrammarmildly
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#104427, answer score: 4
Revisions (0)
No revisions yet.