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 |

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

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?

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 |

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# ...

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 |

In reply to your comments of

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...

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 ...

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

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, ... s_{15})

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?

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, ... s

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.

S -> Xa |

X -> aS | aY | bbb | bX | a

Y -> bY | a | b

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 |

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).

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.