An Introduction to Formal Languages and Automata, 7th Edition

12.4 UNDECIDABLE PROBLEMS FOR CONTEXT-FREE LANGUAGES

The Post correspondence problem is a convenient tool for studying undecidable questions for context-free languages. We illustrate this with a few selected results.

THEOREM 12.8

There exists no algorithm for deciding whether any given context-free grammar is ambiguous.

Proof: Consider two sequences of strings A = (w₁, w₂, …, w_n) and B = (v₁, v₂, …v_n) over some alphabet Σ. Choose a new set of distinct symbols a₁, a₂, …, a_n, such that

$$\left\{a_1,a_2,\mathrm{...},a_n\right\}\cap \Sigma =\varnothing ,$$

and consider the two languages

$$L_A=\left\{w_i{w}_j\cdots w_l{w}_k{a}_k{a}_l\cdots a_j{a}_i\right\}$$

and

$$L_B=\left\{v_i{v}_j\cdots v_l{v}_k{a}_k{a}_l\cdots a_j{a}_i\right\}.$$

Now look at the context-free grammar

$$G=\left(\left\{S,S_A,S_B\right\},\Sigma \cup \left\{a_1,,a_2,\mathrm{...}{a}_n\right\},P,S\right),$$

where the set of productions P is the union of the two subsets: The first ...