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