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.
I’m going to rename some of the non-terminals of $G_1$. Specifically, I’m going to change $K$ to $X$, $C$ to $Z$, $E$ to $Y$, $B$ to $V$, and $A$ to $U$:
$$\begin{align*} &S_1\to aX\\ &X\to bZ\mid cY\\ &Z\to cV\mid D\\ &Y\to bU\mid f\\ &U\to abZ\\ &V\to acY \end{align*}$$
Now compare this with $G_2$ (where I’ve slightly changed the order in which the productions are listed):
$$\begin{align*} &S_2\to aX\\ &X\to bZ\mid cY\\ &Z\to cV\mid D\\ &Y\to bU\mid f\\ &U\to aP\\ &P\to bZ\\ &V\to aQ\\ &Q\to cY\\ \end{align*}$$
Apart from the different initial symbols, the first four rows are identical; the only differences are in what can be derived from $U$ and $V$. Can you show that anything derivable from $U$ or $V$ in $G_1$ is also derivable from $U$ or $V$ in $G_2$?