HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
theseproductionarefreealwaysgrammarsunambiguousonespecialcontext

Problem

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:

  • The non-terminal symbol $S$ can never appear next to itself.



  • e.g. $[\;S \rightarrow aSSb\;|\;\epsilon\;]$ would not be allowed.



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



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



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





  • 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

Solution

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.

Context

StackExchange Computer Science Q#116609, answer score: 9

Revisions (0)

No revisions yet.