- S -> aSb
- S -> aaSb
- S -> ε
Would this grammar be considered ambiguous? I think the answer would be no, considering there is only one variable {S} and there can only be one parse tree generated.
Also, referring to the context-free grammar above, how would you draw all the possible parse trees for the string aaaabbb? This is all I could think of
Any help would be very much appreciated!
The language seem to be strings that contains a sequence of the empty sting and $a$ followed by $b$'s where the number of $a$s is between the number of $b$ (inclusive) and double the number of $b$s inclusive.
It's quite straight forward to show this. First when trying to reduse $a^pb^q$ where $p>2q$ we would get $a^sb^t$ where $s>2t$, $t=q-1$. Eventually we would end up in a string of only one or more $a$s. Similarily if $p<q$ reduction would always contain less $a$s than $b$ and we would end up with only one or more $b$s. And showing that we actually can reduce it otherwise we note that we always can get $t\le s\le 2t$ if $q\le p\le 2q$ and eventually we would end up with $ab$ or $aab$.
The ambiguity is in the application of the first two rules which can be chosen at will as long as there are more $a$s than $b$s (and there's more than $2$ $a$s).
So for example the string $aaabb$ can be reduced as:
$$\begin{align} aaa\epsilon bb \\ aaaSbb && S\rightarrow \epsilon \\ aSb && S\rightarrow aaSb \\ S && S\rightarrow aSb \end{align}$$
or
$$\begin{align} aaa\epsilon bb \\ aaaSbb && S\rightarrow \epsilon \\ aaSb && S\rightarrow aSb \\ S && S\rightarrow aaSb \end{align} $$