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?


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.

  • 2
    $\begingroup$ I thought the most simple regular language was the empty one. ;) $\endgroup$
    – babou
    Mar 4 '15 at 1:25
  • $\begingroup$ Ah, that's excellent. Thanks, Hendrik! $\endgroup$ Mar 4 '15 at 2:35
  • $\begingroup$ @babou Indeed. You made me smile. Nevertheless the concept "empty language" might be very confusing to some. In a recent exam some students noted that $\{a,b,c,d\}$ had $17$ subsets: $2^4$ usual ones, plus the empty set. $\endgroup$ Mar 4 '15 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.