Inherently Ambiguous Context-Free Language

languages

Definition

Inherently Ambiguous Context-Free Language

A context-free language $L$ is called inherently ambiguous if every context-free grammar that generates $L$ is ambiguous.

Examples

A context-free language with no unambiguous grammar

Consider the context-free language $L=L_1\cup L_2$ with:

$$\begin{array}{rl}{L}_1& =\{a^m{b}^m{c}^n\mid m,n\ge 1\}\\ L_2& =\{a^m{b}^n{c}^n\mid m,n\ge 1\}\end{array}$$

Then $L$ is context-free, but it is inherently ambiguous.

A context-free grammar for $L$ is:

$$\begin{array}{rl}S& \to S_1\mid S_2\\ & \\ S_1& \to S_{1}c\mid A\\ A& \to aAb\mid \epsilon \\ & \\ S_2& \to a{S}_2\mid B\\ B& \to bBc\mid \epsilon \end{array}$$

The word $a^n{b}^n{c}^n$ has two different derivations, one via $S_1$ and one via $S_2$.