3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Not every LL(1) is regular, so in general case you cannot. For general CFL this is undecidable, which is provided in the answer. How would you like to automate things more? $\endgroup$ – Evil Jan 31 '16 at 1:18
7
$\begingroup$

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.

$\endgroup$

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.