Is following grammar has language which is inherently ambiguous?

Question

Grammar is as follow:

$S \rightarrow aaAb | aab | A$

$A \rightarrow aaAb | aAb | \epsilon$

I think that this grammar has equivalent unambiguous grammar as follow.

Let’s first rewrite the grammar as below such that this grammar has same language as one in question:

$S \rightarrow aaSb | aSb | \epsilon$

Because this grammar generates $L = \{a^nb^m: m \le n \le 2m\}$

This grammer is just using two production in some order to derive string and then use null production to complete derivation.

So, idea is that we can some how order use of production such that any use of $S \rightarrow aaSb$ production does not come before use of any production of form $S \rightarrow aSb$. And following this idea it’s very easy to generate this grammar.

$S \rightarrow aSb | A$

$A \rightarrow aaAb | \epsilon$

.

Another arguments goes as follow:

Because $2k_1 + k_2 = n$ and $k_1 + k_2 = m$ for some $nonnegetive \space integer \space k_1, k_2$. (here $k_1$ and $k_2$ corresponds to number of use of production of form $S \rightarrow aSb$ and $S \rightarrow aaSb$ respectively.)

After solving the above equations we find that $k_1 = m-n$ hence value of $k_1$ will be unique for any perticular string. Which means that we must have to use some fix number of times the production of form $S \rightarrow aSb$. Which consequenly means that in our last rewritten grammer there is a fix point for a perticular string where you have to perform $S \rightarrow A$.

Please help me with this. I want to know whether this language is inherenly ambigous or not?

Answer 1

Your grammar $$\begin{eqnarray}S &\to& aSb &|& A \\ A &\to& aaAb &|& \epsilon\end{eqnarray}$$ is indeed unambiguous. The production $S \to A$ must occur precisely once in any derivation, and the productions which precede it cannot be replaced with any productions which succeed it or vice versa.