20 views
Let $G_1$ be an unrestricted grammar, and $G_2$ any regular grammar. Show that the problem

$L(G_1) \space\cap L(G_2) = \phi$

is undecidable for any fixed $G_2,$ as long as $L(G_2)$ is not empty.
| 20 views