How can I check that the language of one context-free grammar is a subset of a second context-free grammar?

Question

Could you explain me, how can I check, that the language of first context-free grammar (G1) is a subset of the language of second context-free grammar (G2).

G1 and G2 are two LL(1) grammars with identical alphabets:

{a, b, c, d, f}

Production rules are look like:

A -> αB 

or

A -> α 

and α is a non-epsilon string (of terminal symbols).

Context-free grammar G1:

S1 -> aK
K -> bC|cE
C -> cB|d
E -> bA|f
A -> abC
B -> acE

Context free grammar G2 :

S2 -> aX
X -> bZ|cY
Z -> cV|d
Y -> bU|f
V -> aQ
U -> aP
Q -> cY
P -> bZ

Automatic way is preferred.

In additional, how can I check that the languages of two arbitrary context-free grammars are equal.

Answer 1

Here you have a couple of salient points. Firstly, the grammars are right linear (strictly $G_{1}$ needs some small changes, but they're trivial). This means that the two languages are regular. Given this fact, there's an automated way of determining whether $L(G_{1}) \subseteq L(G_{2})$ or not.

In this case however, things are fairly simple, and we can show a simple mapping between the non-terminals, with only the transitions $A \to abC$ and $B \to acE$ causing a small amount of trouble. If you draw out the finite automata though, you should be able to see the mapping. Doing so, it should be fairly clear that $S_{1}$ maps to $S_{2}$ (obviously), $K$ to $X$, $C$ to $Z$ and $E$ to $Y$. $A$ maps to the pair $U,P$. $U \to aP \to abZ$, and $Z$ already maps to $E$, so you can see the rule is essentially the same in both grammars, just split in $G_{2}$ into an intermediate step. The same observation applies to $B$ and $V,Q$.

Note that in general, we need the fact that $L(G_{1})$ and $L(G_{2})$ are regular, deciding containment for context free languages is undecidable.