# Are these special (one production) Context-Free Grammars always unambiguous?

Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production):

• $$S \rightarrow aSb\;|\;\epsilon$$
• $$S \rightarrow aSbS\;|\;\epsilon$$
• $$S \rightarrow aSaSb\;|\;\epsilon$$
• $$S \rightarrow aaSaaSbb\;|\;\epsilon$$
• $$S \rightarrow aSbScSdSeSf\;|\;\epsilon$$
• etc...

Grammars like these uphold 4 basic rules:

1. The non-terminal symbol $$S$$ can never appear next to itself.
• e.g. $$[\;S \rightarrow aSSb\;|\;\epsilon\;]$$ would not be allowed.
2. The non-terminal symbol $$S$$ can appear at the beginning or end of a production but not on both sides at the same time.
• e.g. $$[\;S \rightarrow SabaS\;|\;\epsilon\;]$$ would not be allowed.
• e.g. $$[\;S \rightarrow Saba\;|\;\epsilon\;]$$ or $$[\;S \rightarrow abaS\;|\;\epsilon\;]$$ would be allowed.
3. The sequence of terminal symbols that exist between each non-terminal $$S$$ cannot all match. (EDIT: This rule is redundant, Rule 4 already ensures that at least two sequences of terminals are non-matching)
• e.g. $$[\;S \rightarrow aSaSa\;|\;\epsilon\;]$$, $$[\;S \rightarrow abSabSab\;|\;\epsilon\;]$$, etc. would not be allowed.
• e.g. $$[\;S \rightarrow aSaSb\;|\;\epsilon\;]$$, $$[\;S \rightarrow abSabSaf\;|\;\epsilon\;]$$, etc. would be allowed.
4. The sequence of terminal symbols at the beginning and end cannot match.
(i.e. $$[\;S \rightarrow ☐_1SaS☐_2\;|\;\epsilon\;]$$ s.t. $$☐_1 \neq ☐_2$$ where $$☐_1$$ and $$☐_2$$ are a sequence of terminal symbols)
• e.g. $$[\;S \rightarrow aSbSa\;|\;\epsilon\;]$$, $$[\;S \rightarrow aaSbSaaS\;|\;\epsilon\;]$$, etc. would not be allowed.
• e.g. $$[\;S \rightarrow aSbSb\;|\;\epsilon\;]$$, $$[\;S \rightarrow aaSbSaxS\;|\;\epsilon\;]$$, etc. would be allowed.
1. The grammar cannot be made to break any of the above rules via a $$S \rightarrow \epsilon$$ production. (Vimal Patel)
• e.g. $$[\;S \rightarrow aSbSaSbS\;|\;\epsilon\;]$$ could become $$[\;S \rightarrow abSabS\;|\;\epsilon\;]$$ if the first and third $$S \rightarrow \epsilon$$, thus violating Rule 4.

Are (Context-Free) Grammars, that follow these 4 rules, always unambiguous? It would seem so. I really don't see any conceivable way that such Grammars could be ambiguous.

(Note: To show why Rule 4 is necessary consider the grammar $$S \rightarrow aSbSa\;|\;\epsilon$$ with the string $$aababaababaa$$. A visual derivation can be found here.)

I've spent a lot of time thinking about this question and have had a hard time finding any way of either proving or disproving it. I've tried showing that Grammars like these are $$LL(1)$$. However, it seems only Grammars of the form $$S \rightarrow aSb\;|\;\epsilon$$ are $$LL(1)$$. Grammars like $$S \rightarrow aSaSb\;|\;\epsilon$$ are not $$LL(1)$$. Maybe I need to use a higher $$k$$ for $$LL(k)$$?

(This question is a follow-up/reformulation of a previous question.)

I would really appreciate any help I could get here.

• If I understand correctly, rules 2 and 3 seem to be redundant (they are implied by rule 4). So, the general form seems to be $S \to \alpha_1 S \alpha_2 S \cdots S \alpha_n | \epsilon$, with the constraints that $\alpha_1 \ne \alpha_n$ and $\alpha_i \ne \epsilon$ for all $i$, where each $\alpha_i$ is a non-empty sequence of terminals. I'm not sure if I'm missing something... – D.W. Nov 3 at 7:42
• I think @meci is trying to convey something else. As per me general form is as follow: $S \rightarrow \alpha_1 S \alpha_2 S ... S \alpha_n | \epsilon$, where $\text{for some i, j } \alpha_i \ne \alpha_j$ and $\text{atmost one Of the }\alpha_1, \alpha_n \text{ can be null }$ and $\alpha_j \ne \epsilon \text{ if } j \ne 1 \text{ and } j\ne n$. And additionally $\alpha_1 \ne \alpha_n$. At mecci please verify it if possible. – Vimal Patel Nov 3 at 10:49
• Yes! Vimal is correct with his interpretation, that is the proper form. – meci Nov 3 at 13:21
• @D.W. it does seem that Rule 3 is redundant if Rule 4 ensures that at least two sequences of terminals are non-matching. – meci Nov 3 at 14:20
• Cool, thanks for the correction. (Since it is required that $\alpha_1 \ne \alpha_n$, there is no need to add the additional requirement that for some $i,j$ we have $\alpha_i \ne \alpha_j$; that is redundant, as we can simply take $i=1$, $j=n$.) – D.W. Nov 3 at 18:57

Here is a simple counter example: $$S \rightarrow aSbSaSbS \space |\space \epsilon$$

and string $$w: abababab.$$ In one case we use last $$S$$ and in other case we use second $$S$$. All other $$S$$ goes to $$\epsilon$$.

Why I was able to get this grammar?

Let's rewrite above grammar with numbers assigned to each $$S$$'s.

$$S \rightarrow aS_1bS_2aS_3bS_4 | \epsilon$$

Now We can virtually eliminate $$S_1$$ and $$S_3$$. (For this whenever we have to derive something from $$S_1$$ or $$S_3$$ we will only derive $$\epsilon$$ from both of this type of $$S$$'s.)

So we get $$S \rightarrow abS_2abS_4|\epsilon$$. (At this time we already have got rid of rule 3.)

Which we were looking for.

• Ahh! I see what you did here. By "canceling out" $S_1$ and $S_3$ you have effectively violated Rule 3 without explicitly doing so. Very interesting! Are there any counterexamples that don't "pseudo-violate" these rules? – meci Nov 3 at 13:20
• I will surely try to find them. And if I succeed then will post them. – Vimal Patel Nov 3 at 13:45
• Thank you so much! – meci Nov 3 at 14:05