Prove that EQCFG G1 G2 are CFGs and LG1 LG2 is undecidab

Prove that EQCFG = { | G1, G2 are CFGs and L(G1) = L(G2)} is undecidable.

Solution

Answer: We will reduce ALLCFG to EQCFG, where ALLCFG = {<G>| G is a CFG and L(G) = }.

Sipser shows that ALLCFG is undecidable.

Dene CFG G0 = (V,,R,S), where V = {S} and S is the starting variable. For each terminal l , the CFG G0 has a rule S lS in R. Also, G0 includes the rule S . For example, if = {a,b}, then the rules in G0 are S aS|bS|. It is easy to see that L(G0) = .

Let R be a TM that decides EQCFG and construct TM S to decide ALLCFG. Then S works in the following manner.

S = “On input <G>, where G is a CFG:

1. Run R on input <G,G0>, where G0 is the CFG dened above with L(G0) = .

2. If R accepts, accept. If R rejects, reject.”

In stage 1, TM R determines if L(G) = L(G0), but because L(G0) = , this determines if L(G) = . In other words, TM S decides ALLCFG, but because ALLCFG is undecidable, this is a contradiction. Hence, we must have that EQCFG is also undecidable