2
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • 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$ – Russell Richie 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$ – Hendrik Jan 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.