How can I prove that $SEQ_{CFG} = \{⟨G,H⟩ \mid \text{$G,H$ are CFGs and $L(G) ⊆ L(H)$}\}$ is decidable ?

I know that $EQ_{CFG} = \{⟨G, H⟩ \mid \text{$G,H$ are CFGs and $L(G) = L(H)$}\}$ is not.

  • 1
    $\begingroup$ You cannot prove that it's decidable, since it's undecidable. $\endgroup$ – Yuval Filmus Jan 16 '19 at 14:17

Another way to see that your problem is undecidable is by reduction from universality. It is known that one cannot decide whether $L(H) = \Sigma^*$. This is just your problem when $L(G) = \Sigma^*$.


We also know that $L(G)=L(H)$ iff both $L(G)\subseteq L(H)$ and $L(H)\subseteq L(G)$.

Now assume $SEQ_{CFG}$ is decidable, then we can decide both ...

  • $\begingroup$ Do you know how to prove $SEQ_{CFG}$ ? $\endgroup$ – ddon-90 Jan 16 '19 at 12:23

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.