495 views
1 votes
1 votes
Does equivalence of CFG decidable ?

That is for two CFG G1 and G2

L(G1)= L(G2)?

And if it is DCFG than is it decidable.

1 Answer

0 votes
0 votes
if its the confirmation that you want then yeah you are right. that equivalence of CFG is not decidable, but equivalence of DCFL is decidable

Related questions

1 votes
1 votes
2 answers
1
1 votes
1 votes
1 answer
2
learner_geek asked Aug 15, 2017
1,374 views
Is complement of language same type or not decidable by CFL and recursive language or not???Grammar is ambiguous or not?Grammar in regular/CFL/rel decidable or not?
3 votes
3 votes
2 answers
3
amrendra pal asked Aug 22, 2017
1,017 views
C = { <G,k | G is a CFG and L(G) contains exactly k strings where k>=0 or k=∞ } . Then C will be-a) decidableb) Turing unrecognizablec) Recursive enumerabled) undecidab...