# Decidability of $SEQ_{CFG} = \{⟨G,H⟩ \mid \text{$G,H$are CFGs and$L(G) ⊆ L(H)$}\}$

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.

• You cannot prove that it's decidable, since it's undecidable. – 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 ...
• Do you know how to prove $SEQ_{CFG}$ ? – ElDon90 Jan 16 at 12:23