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

Question

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.

5. 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.

Answer 1

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.