Welcome! Log In Create A New Profile


Q4 2006

Posted by 35994908 
Announcements Last Post
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
Q4 2006
May 04, 2011 04:01PM
CFG 1:
S -> XY | b
X -> aX | bY | a
Y -> aX | bY | b

CFG 2:
S -> SY | X
X -> bS | bX
Y -> a | aX | ^

Write down a grammar that will generate L1L2:

S -> S1S2
S1 -> X1Y1 | b
X1 -> aX1 | bY1 | a
Y1 -> aX1 | bY1 | b
S2 -> S2Y2 | X2
X2 -> bS2 | bX2
Y2 -> a | aX2 | ^

Question: How do you prove this in both directions (i don't know what that means)?

avatar Re: 2006 Question 4
May 04, 2011 04:09PM
Well for starters I could give a semi-answer to the "prove in both directions" recommendation.

Make an abstraction of what you would prove, and make it fit the following template:


(Turn what it seems natural to need to prove into an "if... then" statement, and then just reverse polarity).

I'll try to make a more useful contribution than that a bit later on.

«later on...» Looks like you're right to not understand what they could mean by 'prove in two directions'. This is a "one way" relationship if you follow the Cohen theorems. P -> Q, and that's it.

Look at page 376 for the basic setup, and then 380 for the theorem ...

... but you obviously did look at it ...

Probably the only missing things is just stating explicitly that you're subscripting to ensure the uniqueness of the terminals and nonterminals of L1 or L2 in the combined language. And of course the subscripts don't change the underlying language at all.

A bidirectional proof would be that given P = L1, L2 in {CFGs} and Q = L1 L2 in {CFGs} , P iff Q. Cohen doesn't seem to claim this, but it's perhaps not an unreasonable possibility? It would say in reverse that you can split any language into "factors", which would be a pretty handy thing to be able to do, ja?

«Another bloomin' edit???»
I think the instruction to pay heed to is : "Write down ..."

A "write down" question assumes you could work it out just by inspection if you know your stuff. Any tips would be aimed at just helping you orientate yourself for the job of writing down the answer ... as you have done here. I think your answer is fine.
Re: 2006 Question 4
May 04, 2011 08:47PM

I completely agree with you. Only one problem, it counts 10 marks. would such a 'short' answer deserve such marks?

P.S. I wrote this using the screen keyboard (no space on my desk for the keyboard), so not much talking from my side.

Don't be different...be the one making a difference
avatar Re: 2006 Question 4
May 04, 2011 09:34PM
Ja, that does look like not much work for 10 marks ...

So maybe look at a "2-way-iff" version, somehow? Going back from some L = L1L2 it follows that the sublanguages are CFL ... ?? My brain is already starting to hurt...

Something tells me that there must be quite a few languages that aren't factorisable? Maybe? Or are there no "prime languages"? Surely these questions are too heavy for us undergrads?

«Edit» Some further thoughts[deleted]. That 10 mark issue nags at me.

The first part of the question is "write down".
The final part of the question is "prove".

Prove that the grammar is correct.
1. It generates every word in the new language.
2. It generates only the words of this language.

So that's the two-directional proof. We just need to abstract a bit to show a conventional "two-way-structure" somehow, eh? Just to become convinced that this really is either P <-> Q, or if not, that it's something that looks a bit like that.
Sorry, only registered users may post in this forum.

Click here to login