2006 Q4

Question 4 (2006)

So L₁ and L₂ could be describe as follows.

The language L₁ S -> L
The language L₂ S -> L

Now take all nonterminals in L₁ and append a subscript 1 and
take all nonterminals in L₂ and append a subscript 2
So you get

S₁ -> L₁ and
S₂ -> L₂

Now create a new CFG of the combined languages and add the line

S -> S₁S₂

Obviously the languages have not been changed by the additional sub script, and no duplicate nonterminals have been created. The CFL create by S₁ followed by the CFL S₂ is still context free, therefore the product of two CFL's is context free/closed.

Now proof that the CFG is still correct (will fill later):
1) All words in L₁L₂ can be generated by S
2) S generates all words in L₁L₂