1
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ Yes you are right. In the second statement the regular language can be given as expression or as finite automaton. Each of these can be effectively translated into the other, so have the same (un)decidability properties. In the same way a context-free language can be given by a grammar or a push-down automaton. $\endgroup$ Dec 18, 2022 at 11:18

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I understand now. Huge thanks. $\endgroup$
    – sockaddr
    Dec 19, 2022 at 2:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.