# Are Context-Free Grammars with only one Production Rule always Unambiguous?

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

• $$S \rightarrow aSb\;|\;\epsilon$$
• $$\require{cancel} \cancel{S \rightarrow aSSb\;|\;\epsilon}$$
• $$S \rightarrow aSbS\;|\;\epsilon$$
• $$S \rightarrow aSaSb\;|\;\epsilon$$
• $$S \rightarrow aaSaaSbb\;|\;\epsilon$$
• $$S \rightarrow aSbScSdSeSf\;|\;\epsilon$$
• $$\require{cancel} \cancel{S \rightarrow aSSbcSd\;|\;\epsilon}$$
• etc...

Are all these Grammars unambiguous? Will every Grammar with only one production rule (not including the epsilon production) always be unambiguous? It would seem so, but I'm not totally sure.

Edit: Vimal Patel has shown that examples like the 2nd and last are, in fact, ambiguous. Discounting these examples and assuming that the non-terminal symbol $$S$$ never appears next to itself, does my belief still hold?

Grammars that only contain one unique terminal symbol could be ambiguous. (ex. $$S\rightarrow aSaSa\;|\;\epsilon$$) However, Grammars with at least two distinct terminal symbols seem like they should always be unambiguous.

Edit II: Vimal Patel has also shown that production rules which both begin and end with the non-terminal $$S$$ are ambiguous (i.e. $$S \rightarrow SaSaSbS\;|\;\epsilon$$) discounting this as well, does my belief still hold?

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)$$. (Illustrated in the parse table below.)

Despite the example Grammar above not being $$LL(1)$$, it still seems to be unambiguous. Maybe it's simply a matter of using a higher $$k$$ for $$LL(k)$$?

In short, are (Context-Free) Grammars with only one production rule (not including the epsilon production) and at least two unique terminal symbols always unambiguous?

I would really love some help, any at all would be greatly appreciated.

• Are you asking something like whether all CFG having only one non-epsilon production which contains two distinct $terminals$ on right hand side of production are always unambiguous? Because all your examples have single $non-terminal$. So they can't have distinct $non-terminal$ on rhs. So you seems to me that you are mistaken in using term $non-terminal$ for term $terminal$. – Vimal Patel Oct 26 '19 at 4:01
• whoops! You are correct, I accidentally put non-terminal when I meant terminal. I fixed it. Thanks for catching that! – meci Oct 26 '19 at 4:15

For instance $$S \rightarrow aSSb | \epsilon$$ is ambiguous.

To see that take $$w: aabb$$. For this string we have following two distinct derivation tree possible. In following derivation trees $$e$$ represents $$\epsilon$$

        S                            S
/  /    | \                  / /    |    \
a  S      S  b                a S     S     b
/ | \ \   \                    |   / / | \
a  S  S b   e                   e  a S  S  b
|  |                              |  |
e  e                              e  e


Second counter example:

Consider grammar $$S \rightarrow SaSbSaS | \epsilon$$ It's easy to see that this grammar is ambiguous. (hint: take $$w: abaaba$$.)

Third counter example:

Consider grammar $$S \rightarrow abSabSab | \epsilon$$. Take $$w = abababababab$$. It's easy to see that there are two distinct derivation trees.

Actually this grammar is directly derived from grammar $$S \rightarrow aSaSa|\epsilon$$ by homomorphism $$h(a) = h(ab)$$.

• Very good point. In that case, I will ask the same question but discount Grammars wherein the non-terminal symbol S appears next to itself. The question has been updated to reflect your observation. – meci Oct 26 '19 at 4:43
• Thank you very much! – meci Oct 26 '19 at 4:51
• Another great point. Your second counterexample seems similar to your first (i.e. you can choose between one of two S non-terminals for the production and the other will take the epsilon production). I've updated my question again to reflect your latest observation. I've put some more thought into it and I truly believe that, from here, there shouldn't be any more ambiguities. Thank you again! – meci Oct 26 '19 at 12:44
• Another excellent point! I was aware that your third counterexample was a possibility but completely forgot to include it as part of my original question. However, I won't add another edit to this post. I think I'll spend some time reformulating my question with these new observations. For now, I'll accept this answer. Thank you so much for your help! – meci Oct 26 '19 at 16:17