Q1 2006

Posted by 35994908
Announcements Last Post
: Programming Students at UNISA School of Computing 06/19/2019 02:01PM
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
 Q1 2006 May 03, 2011 01:54PM Registered: 11 years ago Posts: 50 Rating: 0
Hi,

This is just an attempt to answer the questions of the 2006 exam and to get some feedback and interaction for some of the questions.

Please comment on the attempted answers so we can learn. I don't claim the answers to be correct.

Question 1(a)
The FA - See image below
or

Assuming the FA to be correct the CFG for the language is:

S -> aX | bU
X -> aY | bY
Y -> aX | bZ
Z -> aY | bY | ^
U -> aV | bV
V -> bU | aW
W -> aV | bV | ^

Question 1(b)

Convert to CNF

S -> Xa | Y
X -> aS | aY | bbb | bX
Y -> bY | ^ | a

i) Kill ^ productions

S -> Xa | Y
X -> aS | a | aY | bbb | bX
Y -> bY | a | b

ii) Kill Unit productions

S -> Xa | a | b
X -> aS | a | aY | bbb | bX
Y -> bY | a | b

iii) Convert to CNF

S -> XA | a | b
X -> AS | a | AY | BBB | BX
Y -> BY | a | b
A -> a
B -> b

S -> XA | a | b
X -> AS | a | AY | RB | BX
Y -> BY | a | b
R -> BB
A -> a
B -> b
 Re: Q1 2006 May 03, 2011 02:25PM Registered: 10 years ago Posts: 3,496 Rating: 1
Your question .a is right according to me.

Your question .b lacks a few workings?

First we identify nullABLE productions. Anything that can lead to null qualifies.

P->* Lambda is nullable.

So first the shortest one. Y -> Lambda
Y -> bY -> Lambda ??

Maybe I should stop right there and pause for comments? Is Y -> bY a nullABLE?
 Re: Q1 2006 May 03, 2011 02:42PM Registered: 11 years ago Posts: 50 Rating: 0
Yeah I agree with you,

Y -> bY becomes Y -> b which we already have so it should just be

Y -> a | b
 Re: Q1 2006 May 03, 2011 03:16PM Registered: 10 years ago Posts: 3,496 Rating: 1
Got the book here now, so let's see if I'm reading it right (bypassing lots of theory on the way). Please let me know if I get it wrong.

The only nullables that actually get deleted are the direct Lambda-productions.

In this case we only have Y -> Lambda.

That takes care of the "deleting part".

Now we get to the "adding part". Here all the other nullables become involved.

So what nullables are there?
Y, itself, because of the Y -> bY production.
S, because of S -> Y
X, because of X -> aY

Am I right that a "nullable" is a nonterminal, not a production? (So no need to unravel all productions?)

In other words we just look at what productions need to be added to each of these nonterminals.

#PAUSE# ...
 Re: Q1 2006 May 03, 2011 04:11PM Registered: 11 years ago Posts: 50 Rating: 0

Y, itself, because of the Y -> bY production.
S, because of S -> Y
X, because of X -> aY

Here is my reasoning.
Y becomes Y -> b
S stays S -> Xa | Y because Y could still become either a or b.
X -> aY because the Y could still become either a or b

I could be wrong though...
 Re: Q1 2006 May 03, 2011 04:44PM Registered: 10 years ago Posts: 3,496 Rating: 1
I seem to remember having some success treating this as writing out all the productions (with their lambdas) that you'd get by writing them with their lambdas, but then just scratching the lambda out (as we're entitled to do, just because lambda is null).

So making sure Y can still do its thing without making direct use of lambda:

Y -> a | b | b-lambda = b ... (which, as you say, we already have)

so then that's

Y -> a | b.

And we're agreed on at least one of our nonterminals!

Right so then let me stick my neck out a bit and see if I can fix the other nullables to still do what they were able to do when they made use of the lambda production eventually. (these would be additional..)

X -> aY -> a-lambda = a, which we already have ...
(it can still do X -> aY -> aa or ab so it's just this lambda case we need to add)
and then what about X -> bX? (Since that RHS X is a nullable)

X -> bX -> baY -> ba-lambda = ba, which is new.

I'd better pause again there, eh? Is my X -> ba OK? Or is that just something I get from "normal x"? I think I might be wrong here ...
 Re: Q1 2006 May 04, 2011 11:08PM Registered: 12 years ago Posts: 67 Rating: 0
Thanks for posting your answer for Question 1 (a) I got the same result so either great minds think alike or fools never differ

For Question 1 (b) I already made a mistake in step 1. So I redid it and got a different answer then you and would like to discusses this(I marked my question in step 2 in brackets):

S -> Xa | Y
X -> aS | aY | bbb | bX
Y -> bY | ^ | a

Step 1: Eliminate the ^-Production

S -> Xa | Y
X -> aS | aY | bbb | bX | a (slow_eddy: I forgot the "a" here, but after reading through your post I saw the errors in my way, thanks)
Y -> bY | a | b

Step 2: Eliminate the unit productions

S -> Xa | bY | a | b (Why did you left out the bY production?)
X -> aS | aY | bbb | bX | a
Y -> bY | a | b

Step 3: Rewrite production in the correct form

S -> XA | BY | a | b
X -> AS | AY | BBB | BX | a
Y -> BY | A | B
A -> a
B -> b

CFG in CNF:

S -> XA | BY | a | b
X -> AS | AY | RB | BX | a
R -> BB
Y -> BY | A | B
A -> a
B -> b
 Re: Q1 2006 May 05, 2011 01:44PM Registered: 10 years ago Posts: 3,496 Rating: 1
@ d-_-b
Thanks. It's always reassuring to get confirmation that at least someone else finds one's train of thought makes sense.

The reason for the missing bY is simply that I though I'd better pause (deal with one thing at a time). I just never got there. Me, I'm still back there among the folk who're shouting at the lambda.

So now I'd better quickly catch up and see if I can agree with the unit production step.

If we have X => .. => .. => N <--- all on its own, a NONterminal...
Then find out what non-units N produces.... and ...

Let X produce those without having to go all the way to N like that. (String, MoreString, stringy, ... s15)

So the "ADD" part comes first.

Once we've added those non-units to any X that reaches them by some path, we can DELETE them from the unit production's nonterminal-as-LHS.

OK so now let me try and follow the recipe in some detail.

We separate the Units from the Decent Folk.

Decent Folk.

S -> Xa |
X -> aS | aY | bbb | bX | a
Y -> bY | a | b

Units.

S -> Y

We have just one person with flatulence in this concert hall. We must add new productions to S to go direct to where S -> Y -> would've taken us indirectly, then.

S -> bY | a | b (in addition to Xa)

And so finally I now check to see whether I've done it right, using your answer as the litmus.

Ah! Right! And I can give a better answer to "why did you leave out bY"? Um... shuffle ... well actually I messed up, that's why.

Er... OK I'd better add Y -> bY doesn't just become Y -> b.
Example Y -> bY -> b(bY) -> b(b(bY)) ... and so on. It allows formation of b*.

I'll chicken out of finishing for now. Maybe someone else wants to double check that the final step is also right?
 Re: Q1 2006 May 05, 2011 09:10PM Registered: 11 years ago Posts: 50 Rating: 0
Thanks for the feedback! It really helps!

Man, I see the error of my ways, thanks for pointing it out! You are correct. I just hope to not make silly mistakes like that in the exam. Rather now than later!
 Re: Q1 2006 May 05, 2011 10:12PM Registered: 10 years ago Posts: 3,496 Rating: 1
That's the way we learn. "Open Source". Make all our mistakes out in the open, and share the benefit of the bug fixes in all sorts of ways.

Now I think I've somehow led myself down a dead end, running over this a second or third or fifth time. This is what's happening when I try to replace all the missing lambda (L) productions.

X ->aY -> abY -> abL = ab

X -> aS -> aXa -> aaYa -> aaLa -> aaa

X-> bX -> baS -> baY -> baL -> ba

... it just goes on and on and on and on ...

Someone please see if you can figure out what I'm doing wrong here. (And let's hope I'm making some mistake, because this is looking a bit of a nightmare as it balloons like this).

... In fact if you're tempted to tell me I'm right, please sharpen your pencil and make me a better deal.

(It's not often a man wants to be wrong, but sometimes it really is for the better).
Sorry, only registered users may post in this forum.