Question: Here is an incorrect proof that E Q C F G is decidable. E Q C F G is in fact not decidable. Not a

Here is an incorrect proof that EQCFG is decidable. EQCFG is in fact not decidable.
Not a proof: Construct a TM as follows:
On input (:G1,G2:) :
Since CFLs are closed under complement, intersection, and union, we can construct a CFG G for (:bar(L(G2))}
Run MECFG on G and return the result.
This TM accepts inputs (:G1,G2:) with L(G1)=L(G2) and rejects inputs (:G1,G2:) with L(G1)L(G2), so it decides EQCFG.
Which of the following are issues with the proof?
A.ECFG is not decidable so MECFG does not halt on all inputs.
B. CFLs are not closed under union, so we can't necessarily construct G.
C. CFLs are not closed under intersection, so we can't necessarily construct G
 Here is an incorrect proof that EQCFG is decidable. EQCFG is

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!