Is the equivalence problem of a CFG and a FSM decidable?

Question

I have the following problem:

Given a context-free grammar $\mathcal{G}$ and a finite state automaton $\mathcal{A}$, where both are over the alphabet $\Sigma=\{0, 1\}$. Is it decidable whether $L(\mathcal{G})=L(\mathcal{A})$?

I assume this is undecidable, since I already know the following fact:

It is undecidable whether $L(\mathcal G)=R$ for CFG $\mathcal G$ and regular language $R$.

Therefore I think it should be impossible to decide whether a CFG and a FSM generate the same language. Is my assumption correct?

Answer 1

Yes, your assumption is right regularity of context-free languages is undecidable.

You can look at the problem like this, If $L(G) = L(A)$ then we can say $L(G) \subseteq L(A)$ and $L(A) \subseteq L(G)$ which can also be written as

$L(G) \cap L(A)^{c} = \emptyset$ and $L(A) \cap L(G)^{c} = \emptyset$

Now for the first equation, regular languages are closed under complement so it comes down to checking the emptiness of $CFL$ $\cap$ $Reg$ which is equivalent to the emptiness of $CFL$ which is decidable.

Similarly, for the second part, we need to check the emptiness of $Reg$ $\cap$ $CSL$(as $CFL$ are not closed under complement) which is equivalent to the emptiness of $CSL$ which is undecidable.

Hence the equivalence problem of a CFG and an FSM is undecidable.