Welcome! Log In Create A New Profile


Drawing PDA's

Posted by ian.coetzer 
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
Drawing PDA's
February 25, 2009 11:07PM

In assignment 2 question 4 we are asked to draw a PDA.
Can we exclude the REJECT states and only show the way to the ACCEPT state?

avatar Re: Drawing PDA's
February 26, 2009 10:10AM

I'm nowhere near ready to move on to assignment 2. But even from what I've done for assignment 1 leads me to believe that we can.

I'm busy looking at PDA's in Chapter 14/15, and they don't seem to have any reject states anymore. I suppose it all depends on whether you want your string to crash or to be rejected, and seeing that they haven't introduced consequences for strings crashing I'd say that at the moment both outcomes are the same.

Re: Drawing PDA's
February 26, 2009 05:40PM
Whoa, someone's speeding through the work! From my understanding of what I've read so far on PDAs, I think you would have to include the REJECT state but on the other hand, I'm only on page 302 smiling smiley
avatar Re: Drawing PDA's
February 26, 2009 07:37PM
Found your answer: Page 327
A PDA is in conversion form if it meets all the following conditions:
1. There is only one ACCEPT state.
2. There are no REJECT states.
And CFG is for context-free languages which is handled in Chapter 17 where our PDA questions comes from.
Re: Drawing PDA's
March 02, 2009 06:31PM
Thanks for all the replies, well I only have two subjects this year so I'm managing to work through the study material quicker than the rest of you I suppose?
avatar Re: Drawing PDA's
March 16, 2009 09:50AM
You don't need to add REJECT states to a PDA for it to be a valid PDA. If the PDA gets to a point where it cannot proceed and don't have a REJECT state to go to, the "program" crashes. It says so in the book (can't find the reference now).
Sorry, only registered users may post in this forum.

Click here to login