[Solved]: Is equivalence of a CFG and an RG undecidable?

Problem Detail: 

I know that the equivalence of two context-free grammars is undecidable, but what about the equivalence of a regular grammar and a context-free grammar?

Asked By : Russell Richie

Answered By : Hendrik Jan

It is undecidable whether for a given CFG $G$, $L(G)=\Delta^*$, the set of all strings (over the terminal alphabet of $G$). That answers your question, by chosing the most simple regular grammar.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40041

3.2K people like this

 Download Related Notes/Documents