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 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$ – ElDon90 Jan 16 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.