Oct 2006 exam Q4 help

Quote

Context-free languages are closed under product. Consider the languages L1 and L2 generated by the two CFGs below. Write down a grammar that will generate L1L2, and prove that your grammar is correct. (Hint: The proof should be done in two directions.)

CFG1
S -> aS | bX
X -> aY | bX
Y -> bX | b

CFG2
S -> aY | b | /\
X -> aX | b
Y -> bX | a | /\

Solution
First give the nonterminals of the different CFGs different subscripts:

CFG1
S1 -> aS1 | bX1
X1 -> aY1 | bX1
Y1 -> bX1 | b

CFG2
S2 -> aY2 | b | /\
X2 -> aX2 | b
Y2 -> bX2 | a | /\

Then combine all productions into a product CFG (L1L2), with a new start production:

S -> S1 S2
S1 -> aS1 | bX1
X1 -> aY1 | bX1
Y1 -> bX1 | b
S2 -> aY2 | b | /\
X2 -> aX2 | b
Y2 -> bX2 | a | /\

a) Prove that the new CFG generates all words in L1L2:
The start production introduces the working string S1 S1 , after which productions from lines 2->4 must be used to generate a word from S1 and productions from lines 5->7 to arrive at a word from S2 . Words from L1 and L2 are thus concatenated (in that order). This is the only way in which words can be produced, and these words are precisely those in L1L2. Because different subscripts are given in lines 2->4 and 5->7, no overlapping of productions is possible, so no extra words are generated.

b) Prove that all words in L1L2 can be generated by the CFG:
Words in the language L1L2 begin with a word from L1, followed by a word from L2. The start production in the above CFG can be used to achieve a working string of this form. From there on, all words in L1 can be placed in the first half, since all of L1’s productions are in the new CFG (with the addition of subscripts, which don’t change the language generated). Similarly for L2, all words from that language can be generated and placed after an L1 word.

From a) and b) above, we can conclude that the new CFG generates the product language.