patternMinor
Are these special (one production) Context-Free Grammars always unambiguous?
Viewed 0 times
theseproductionarefreealwaysgrammarsunambiguousonespecialcontext
Problem
Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production):
Grammars like these uphold 4 basic rules:
(i.e. $[\;S \rightarrow ☐_1SaS☐_2\;|\;\epsilon\;]$ s.t. $☐_1 \neq ☐_2$ where $☐_1$ and $☐_2$ are a sequence of terminal symbols)
- $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.
$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.