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

Problem Detail: 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.

Asked By : Pu Vexi

Answered By : Luke Mathieson

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.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52495

Leave a Reply