1
$\begingroup$

Got a final coming up, so I gotta get this concept down.

Given $A= \{(G_1,G_2 \mid G_1$ and $G_2$ are two CFG's and $L(G_1)=L(G_2) \}$. Is $A$ decidable?

Would it be sufficient to take an undecidable language such as $B= \{x \mid L(M_x)$ is a CFG $ \}$. Then reduce it to A with function $f(x) = G'_{M_x}$?

$\endgroup$
2
$\begingroup$

I don't really understand your reduction, but there is a very easy reduction from $ALL_{CFG}=\{G| G \text{ is a CFG and } L(G)=\Sigma^*\}$. Given $G$, Simply output $(G,G_{\Sigma^*})$, where $G_{\Sigma^*}$ is a (concrete) grammar that generates every word.

And the problem $ALL_{CFG}$ can be shown to be undecidable with a very nice (but elaborate) reduction from the word problem for TMs.

| cite | improve this answer | |
$\endgroup$

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.