Welcome! Log In Create A New Profile


assignment 4

Posted by Anonymous User 
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
Anonymous User
assignment 4
August 20, 2007 10:41AM
hi, is anyone making any head way for this assignment? I am stuck on the earley algorythm as well as the last question - the one for while and during
Re: assignment 4
August 20, 2007 01:47PM

I am also struggling with the Early algorithm

Going to have to email the lecturer for some explanations
Anonymous User
Re: assignment 4
August 20, 2007 02:13PM
did you understand the while/during question?

If you get any feedback can you let me know? Also, have you received any marked assignment back?
Re: assignment 4
August 20, 2007 03:01PM
only assignment 1... and i haven't started this one yet sad smiley
Anonymous User
Re: assignment 4
August 20, 2007 03:41PM
did you actually get assignment 1 back? I got a mark but thats it
Re: assignment 4
August 20, 2007 03:57PM
I also didn't get Assignment 1 back...

Haven't go to the while/during question yet.
Will let you know if i get any feedback regarding this assignment.

Re: assignment 4
August 23, 2007 11:27PM
Question 10.1 refers to figure 10.7...is it supposed to refer to figure 10.6?
Anonymous User
Re: assignment 4
August 24, 2007 08:46AM
if thats the earley algorythm, then yes, it should be 10.6. If its another questio nthen I am not sure - I don't have the textbook with me today
Re: assignment 4
August 26, 2007 06:09PM
My recognizer is working fine, but I'm completely baffled by the parse tree requirement. I understand, sort of, the idea of having a back pointer to the state that was used in the derivation of the completed state, in other words, using the example on page 386, I understand, say, how state S10 has a back pointer to S9, and why S20 has a back pointer to S18...but I do NOT understand how S21 has TWO backpointers, to S14 and S19 - why isn't it just to S19?

Perhaps you've found a place on the internet that explains it better than the textbook?
Anonymous User
Re: assignment 4
August 27, 2007 08:59AM
I haven't even figured the normal parser out sad smiley I understand the theory but my practical coding part is not up to scratch
Re: assignment 4
August 29, 2007 10:29AM
I kinda understand the earley algorithm and the parse tree addition to it - well i understand it enough to code it.

Let me try to explain it the way i understand it...

S21 is derived from running the completer on S19 [so one of its backpointers is S19].
Furthermore, we note how S21 is derived by running the completer on S19 - This is done by finding "all previously created states that were looking for this (S19) grammatical category at this position in the input". When these previous states are found, we create a copy of this state and advance the dot.
Now, in the case of S21, one of the states that was expecting S19, was S15. So we look at the backpointers that S15 already has, and append all its backpointers to S21 (that being just S14). Then i assume we do this recursively, and append also the backpointers of S14 to S21... etc

Hope it helps
Re: assignment 4
August 29, 2007 04:11PM
Hey Peeps...

I'm struggling with the Early algorithm... anyone please share some light...
Re: assignment 4
August 29, 2007 04:39PM
Thanks Lois, I'll see if I can code this up

Using a longer sentence ("does this flight include a meal"winking smiley, I get this chart

S0 Gamma->* S [0,0] Dummy Start State
S1 S->* NP VP [0,0] Predictor
S2 S->* Aux NP VP [0,0] Predictor
S3 S->* VP [0,0] Predictor
S4 NP->* Det Nominal [0,0] Predictor
S5 NP->* ProperNoun [0,0] Predictor
S7 VP->* Verb [0,0] Predictor
S8 VP->* Verb NP [0,0] Predictor
S6 Aux->does * [0,1] Scanner
S9 S->Aux * NP VP [0,1] Completer
S10 NP->* Det Nominal [1,1] Predictor
S11 NP->* ProperNoun [1,1] Predictor
S12 Det->this * [1,2] Scanner
S13 NP->Det * Nominal [1,2] Completer
S14 Nominal->* Noun [2,2] Predictor
S15 Nominal->* Noun Nominal [2,2] Predictor
S16 Noun->flight * [2,3] Scanner
S17 Nominal->Noun * [2,3] Completer
S18 Nominal->Noun * Nominal [2,3] Completer
S19 NP->Det Nominal * [1,3] Completer
S20 Nominal->* Noun [3,3] Predictor
S21 Nominal->* Noun Nominal [3,3] Predictor
S22 S->Aux NP * VP [0,3] Completer
S23 VP->* Verb [3,3] Predictor
S24 VP->* Verb NP [3,3] Predictor
S25 Verb->include * [3,4] Scanner
S26 VP->Verb * [3,4] Completer
S27 VP->Verb * NP [3,4] Completer
S28 S->Aux NP VP * [0,4] Completer
S29 NP->* Det Nominal [4,4] Predictor
S30 NP->* ProperNoun [4,4] Predictor
S31 Det->a * [4,5] Scanner
S32 NP->Det * Nominal [4,5] Completer
S33 Nominal->* Noun [5,5] Predictor
S34 Nominal->* Noun Nominal [5,5] Predictor
S35 Noun->meal * [5,6] Scanner
S36 Nominal->Noun * [5,6] Completer
S37 Nominal->Noun * Nominal [5,6] Completer
S38 NP->Det Nominal * [4,6] Completer
S39 Nominal->* Noun [6,6] Predictor
S40 Nominal->* Noun Nominal [6,6] Predictor
S41 VP->Verb NP * [3,6] Completer
S42 S->Aux NP VP * [0,6] Completer

I'd be interested to see what backpointers you get from S42 (assuming you get the same chart, that is!)
Anonymous User
Re: assignment 4
August 29, 2007 04:40PM
sorry, I don't know either, I am going to be looking at mine now.... if I get any bright sparks I will let you know smiling smiley
Re: assignment 4
August 30, 2007 12:14AM
Well, I eventually figured it out. The example in the textbook is spectacularly obtuse and in my opinion simply serves to confuse. For me, the solution was to simply store two pointers for each new state generated by the completer step: a pointer to the completed state that we are trying to match against, and a pointer to the older incomplete state that matches. So for instance, state S21 is generated by completed state S19, while the completer step identifies state S15 as the incomplete state that matches. Similarly state S11 has back pointers to S3 and S9.

To generate the parse tree, one recursively backtracks through these back pointers - eventually the pointers will point to a word (from a scanner production) or to nothing (by nothing, I mean a dead-end state, i.e., a state that is not producing a word in our sentence and does not have any backpointers). For instance, using the examples above, S15 points to S14, which is the word "that", while S3 points to nothing and is ignored.

Of course, I may be barking up the wrong tree - but it seems to be working correctly with quite large grammars and sentences.
Re: assignment 4
August 30, 2007 10:08AM
Hey, as long as it works! smile

I still need to test mine with a different grammar and sentence. I am praying very hard that it doesn't crash! grinning smiley
Anonymous User
Re: assignment 4
August 30, 2007 10:43AM
I haven't even written mine yet sad smiley
Re: assignment 4
August 30, 2007 10:51AM
I think if you understand the algorithm completely you can write the code very swiftly. I had no idea how the algorithm worked and attempted to figure it out while coding it. As a result it took me many days to write the code, and I'm still not sure I fully understand the algorithm tongue sticking out smiley If I rewrote it now it would probably be half the length, if not shorter.
Anonymous User
Re: assignment 4
August 30, 2007 10:56AM
Re: assignment 4
August 31, 2007 10:03AM
Is it just me, or is submitting this assignment going to be tricky? My email is being bounced, and my.unisa.ac.za is not answering...
Re: assignment 4
August 31, 2007 10:19AM
My email also keeps getting blocked. I have contacted the IT department in my company to have it released. In the meantime, just email the lecturer to let her know that the email is being blocked, and that you will keep trying. I was having the same problem for Assignment 02. She was very understanding. She will even give you confirmation when she receives the programs files. Also, she had told me that Unisa also has a filter that blocks some of her incoming emails. So if you make sure it gets sent on your side, the rest is up to Unisa.
Anonymous User
Re: assignment 4
August 31, 2007 11:35AM
I submitted my assignment yesterday - without the programmign question in it. I got a mesage from unisa saying my assignment was late but would still be accepted. this is after the fac tath tin march I sent them about 3 emails sayign the submission date on myUnisa was wrong. With assignment 2 I had to send the code to lecturer about 3 times, someones firewall kept removing the code. I hope though you guys manage to get your stuff through today smiling smiley
Re: assignment 4
August 31, 2007 01:36PM
What I mean is, my emails to the lecturer are being bounced back. Any my browser times out trying to connect to my.unisa.ac.za. It's been like this since last night.

Edit: turns out if I use https rather than http, I can get to my.unisa.
Anonymous User
Re: assignment 4
September 04, 2007 08:27AM
Hi, out results for COS460 and COS405 have been fixed - the % is set to 100 now - well, mine was smiling smiley
Re: assignment 4
September 04, 2007 08:33AM
Mine too!

Woohoo!!! thumbs up smiley
Anonymous User
Re: assignment 4
September 04, 2007 11:24AM
Sorry, only registered users may post in this forum.

Click here to login