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

Question

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.

Answer 1

Unfortunately, your conjecture is wrong.

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)$.