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 


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$?

  • $\begingroup$ Thank you for the prompt reply, @Brian. Could you explain me can I do it automatically? And how can I check two arbitrary context-free grammars for their language equality. $\endgroup$ – Pu Vexi Jan 31 '16 at 0:52
  • $\begingroup$ @PuVexi: You’re welcome. In general it’s a very hard problem, and I don’t know any relatively mechanical procedure; this particular problem appears to have been very carefully tailored to make it manageable. Whoever designed it wanted you to recognize that one grammar was almost a copy of the other, just with different names for the non-terminals. $\endgroup$ – Brian M. Scott Jan 31 '16 at 4:19

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.