# Oct 2006 exam Q4 help

Posted by brettc
Announcements Last Post
SoC Curricula 09/30/2017 01:08PM
Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
School of Computing Short Learning Programmes 11/24/2014 08:37AM
Unisa contact information 07/28/2011 01:28PM
 Oct 2006 exam Q4 help October 27, 2009 10:15PM Registered: 12 years ago Posts: 184 Rating: 0
I'm having some trouble with this question. I can get a grammar using the method on pg 380 of Cohen, but I'm not sure how to go about proving that the grammer is correct. It says it should be done in two directions too...which 2 directions?
Do we have to create the grammar and the machine? First time I'm seeing a question like this.
 Re: Oct 2006 exam Q4 help October 27, 2009 10:58PM Registered: 14 years ago Posts: 3,015 Rating: 5

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.
 Re: Oct 2006 exam Q4 help October 28, 2009 08:30AM Registered: 12 years ago Posts: 184 Rating: 0
Cool thanks
 Re: Oct 2006 exam Q4 help October 28, 2009 07:11PM Registered: 14 years ago Posts: 613 Rating: 0
Nice explanation
 Re: Oct 2006 exam Q4 help October 29, 2009 06:34AM Registered: 14 years ago Posts: 3,015 Rating: 5
Got it somewhere in some notes someone sent me at some stage ....
 Re: Oct 2006 exam Q4 help October 29, 2009 05:56PM Registered: 14 years ago Posts: 613 Rating: 0
LOL, thought you might've typed that whole thing out
 Re: Oct 2006 exam Q4 help October 29, 2009 07:47PM Registered: 14 years ago Posts: 3,015 Rating: 5
Too lazy for that. Excellent at gathering other people's notes or tut's, passing them on & not using it myself...
 Re: Oct 2006 exam Q4 help October 30, 2009 10:57PM Registered: 13 years ago Posts: 137 Rating: 0
thanks
Sorry, only registered users may post in this forum.