6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – D.W. Nov 3 at 7:42
  • 1
    $\begingroup$ 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. $\endgroup$ – Vimal Patel Nov 3 at 10:49
  • $\begingroup$ Yes! Vimal is correct with his interpretation, that is the proper form. $\endgroup$ – meci Nov 3 at 13:21
  • $\begingroup$ @D.W. it does seem that Rule 3 is redundant if Rule 4 ensures that at least two sequences of terminals are non-matching. $\endgroup$ – meci Nov 3 at 14:20
  • 2
    $\begingroup$ 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$.) $\endgroup$ – D.W. Nov 3 at 18:57
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – meci Nov 3 at 13:20
  • $\begingroup$ I will surely try to find them. And if I succeed then will post them. $\endgroup$ – Vimal Patel Nov 3 at 13:45
  • $\begingroup$ Thank you so much! $\endgroup$ – meci Nov 3 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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