Question

Show that the language A is inherently ambiguous.

$\mathbf{A}\mathbf{=}\mathbf{\left\{}{\mathbf{a}}^{\mathbf{i}}{\mathbf{b}}^{\mathbf{j}}{\mathbf{c}}^{\mathbf{k}}\mathbf{\right|}\mathbf{i}\mathbf{=}\mathbf{j}\mathbf{or}\mathbf{j}\mathbf{=}\mathbf{k}\mathbf{where}\mathbf{i}\mathbf{,}\mathbf{j}\mathbf{,}\mathbf{k}\mathbf{\ge }\mathbf{0}\mathbf{\}}$

Short answer

$\mathrm{A}=\left\{{\mathrm{a}}^{\mathrm{i}}{\mathrm{b}}^{\mathrm{j}}{\mathrm{c}}^{\mathrm{k}}\right|\mathrm{i}=\mathrm{j}\mathrm{or}\mathrm{j}=\mathrm{k}\mathrm{where}\mathrm{i},\mathrm{j},\mathrm{k}\ge 0\}$

This grammar is inherently ambiguous grammar is proved.

Step-by-step solution

Step 1:

Inherently ambiguous grammar is a language in which no unambiguous grammar is possible. It means that for all string of a language there exist more than one left most derivation or more than one right most derivation or more than one parse tree is called ambiguous grammar.

ambiguous grammar from which elimination of ambiguity is not possible is called Inherently ambiguous grammar.

Proving that the given grammar is inherently ambiguous grammar.

$\mathrm{A}=\left\{{\mathrm{a}}^{\mathrm{i}}{\mathrm{b}}^{\mathrm{j}}{\mathrm{c}}^{\mathrm{k}}\right|\mathrm{i}=\mathrm{j}\mathrm{or}\mathrm{j}=\mathrm{k}\mathrm{where}\mathrm{i},\mathrm{j},\mathrm{k}\ge 0\}$

Here the strings of language $\mathrm{L}\left(\mathrm{A}\right)$from the grammar A is $\mathrm{L}\left(\mathrm{A}\right)$.

$\mathrm{L}\left(\mathrm{A}\right)=\{\mathrm{abc},\mathrm{aabbcc},\mathrm{aaabbbccc}\}$

Suppose that $\mathrm{G}=(\mathrm{V},\mathrm{T},\mathrm{\Sigma },\mathrm{S})$is a context free grammar for Language, and let be the constant specified for graph in Ogden’s lemma.

Assume that,

$\mathrm{p}>3.$

After that let’s consider the string.

$\mathrm{z}={\mathrm{a}}^{\mathrm{p}}{\mathrm{b}}^{\mathrm{p}}{\mathrm{c}}^{\mathrm{p}+\mathrm{p}}$

in the given language. After that suppose mark all the positions of ‘a’ as distinguished.

Let $\mathrm{u},\mathrm{v},\mathrm{w},\mathrm{x},\mathrm{y}$be the five parts of $\mathrm{z}$as specified in the Ogden’s lemma.

Show that,

$\mathrm{v}={\mathrm{a}}^{\mathrm{t}}$

$\mathrm{x}={\mathrm{b}}^{\mathrm{t}}$, for some t.

Another string with all the positions of ‘c’ as distinguished. Using Ogden’s lemma there is a non-terminal B that in any grammar there is some string having at least two distinct derivations. So, by the definition, the language is inherently ambiguous.

It means that for all string of a language there exist more than one left most derivation or more than one right most derivation or more than one parse tree and here no unambiguous grammar is possible. and it is also specified in the Ogden’s lemma hence it is proved that the language$\mathrm{A}=\left\{{\mathrm{a}}^{\mathrm{i}}{\mathrm{b}}^{\mathrm{j}}{\mathrm{c}}^{\mathrm{k}}\right|\mathrm{i}=\mathrm{j}\mathrm{or}\mathrm{j}=\mathrm{k}\mathrm{where}\mathrm{i},\mathrm{j},\mathrm{k}\ge 0\}$ isinherently ambiguous grammar.