I'm having serious issues fining an unambiguous version of a particular grammar. I've looked online for help for this particular problem and for general methods for finding unambiguous versions of grammars, and though I understand the concept, I can't seem to figure this out. Any help/advice? I keep getting really close then finding something that doesn't fit. Here is the grammar in question:

S -> aS | bS | Sa | Sb | aa


1 Answer 1


The language of the grammar $G$ presented here is regular and its corresponding regular expression is $$r = (a \mid b)^*aa(a \mid b)^*.$$ Now, convert the regular expression to a minimal finite automaton and use this question to convert the automaton to an unambiguous regular grammar, which is always possible. In the end you can get something like this:

$$ \begin{align} S &\rightarrow aA \mid bS \\ A &\rightarrow aB \mid bS \mid a \\ B &\rightarrow aB \mid bB \mid \epsilon \end{align} $$

Proof that $\mathscr{L}(r) = \mathscr{L}(G)$: (1) Let $s \in \mathscr{L}(r)$, hence $s = x aa y$, where strings $x,y$ consist of characters $x_i, y_j \in \Sigma, i = [1..m], j = [1..n], m = |x|, n = |y|$. There is a derivation of $s$: $$S \rightarrow x_1S \rightarrow x_1x_2S \rightarrow ... \rightarrow x_1...x_mS = xS \rightarrow xSy_n \rightarrow xSy_{n-1}y_n\rightarrow ... \rightarrow xSy_1...y_n = xSy \rightarrow xaay.$$ Thus $s = xaay \in \mathscr{L}(G)$ and $\mathscr{L}(r) \subseteq \mathscr{L}(G)$.

(2) Let $s \in \mathscr{L}(G)$. This means there exists some derivation $$S \rightarrow \alpha_1 \rightarrow \alpha_2 \rightarrow ... \rightarrow \alpha_p = s.$$ Observe that the only way to make the non-terminal $S$ disappear is to use the rule $S \rightarrow aa$ and it must be the last step of the derivation: $$S \rightarrow \alpha_1 \rightarrow ... \rightarrow \alpha_{p-1} = xSy \rightarrow \alpha_p = s = xaay,$$ where $x,y$ are some strings of terminals. Thus $s = xaay \in \mathscr{L}(r)$ and $\mathscr{L}(G) \subseteq \mathscr{L}(r)$, resulting in $\mathscr{L}(G) = \mathscr{L}(r)$. Qed.

  • $\begingroup$ This part doesn't seem like it would work... s=xaay Because it wouldn't make it possible for a string like, say, "babaa" because it implies that there has to be some string "y" on the right side of "aa." I've gotten that far before, but can't work out a parse tree that would make "xaay" work. $\endgroup$
    – Olivia
    Feb 11, 2016 at 16:11
  • 1
    $\begingroup$ Notice that $j = [1..n], n = |y|$. If $y$ is empty, then $|y| = 0$, so $y_1...y_0$ just means the empty string, it's a pretty common convention. The same thing works for $x$. In case of $babaa$, $s = xaay$, where $x = bab$, $y = \epsilon$. $\endgroup$ Feb 11, 2016 at 16:16

Your Answer

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

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