2
$\begingroup$

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

enter image description here

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.

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$ Oct 26, 2019 at 4:01
  • $\begingroup$ whoops! You are correct, I accidentally put non-terminal when I meant terminal. I fixed it. Thanks for catching that! $\endgroup$
    – meci
    Oct 26, 2019 at 4:15

1 Answer 1

5
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – meci
    Oct 26, 2019 at 4:43
  • $\begingroup$ Thank you very much! $\endgroup$
    – meci
    Oct 26, 2019 at 4:51
  • $\begingroup$ 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! $\endgroup$
    – meci
    Oct 26, 2019 at 12:44
  • 1
    $\begingroup$ 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! $\endgroup$
    – meci
    Oct 26, 2019 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.