Prove that the following two languages are undecidable.

a. OVERLAP_CFG = {〈G,H〉| G and H are CFGs where L(G) ∩ L(H) ≠ ⌀}.

Adapt the hint in Problem 5.21.

b. PREFIX-FREE_CFG = {〈G〉| G is a CFG where L(G) is prefix-free}.

Problem 5.21.

Let AMBIG_CFG = {〈G〉| G is an ambiguous CFG}. Show that AMBIGCFG is undecidable. Use a reduction from PCP. Given an instance

 

of the Post Correspondence Problem, construct a CFG G with the rules

where a₁, . . . , a_k are new terminal symbols. Prove that this reduction works.

Transcribed Image Text:

tk P =