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?
$\begingroup$
$\endgroup$
0
Add a comment
|
$\begingroup$
$\endgroup$
3
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$ @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
