Oct 2006 Exam Question 2.

Okay, my attempt at the deterministic PDA, please take a look and let me know if you agree with this solution.

2006 2.

*** Question 2 ***

thx
(if you experience any problems with these links then please let me know! so that I can fix them)

Looks good to me.
Pretty much the same as mine.

*Edit* Just one question: Do we have to cater for reading/popping something unexpected (like say a /\) and moving to a reject state?
I just noticed that you didn't do that, it would save a lot of time if it's not required.

If a state in a PDA has no edge leading from it that can read a character that is on the TAPE (from a READ) or in the STACK (from a POP) then the word is rejected.

You need to read an /\ after reading the last a (in addition to popping an /\). Otherwise your PDA accepts (ac)ⁿ(bc)ⁿa(a+b)*.

--
"A man is the less likely to become great the more he is dominated by reason: few can achieve greatness - and none in art - if they are not dominated by illusion." Mr. Doctor

Great! thanks for spotting that error would have cost me a point or two!
Will have to remember that in the exams, I do sometimes assum that the machine knows that the next Read will result in an empty / null character being red.
But we have to force the machine to carry on reading since it cannot predict what the next character will be and that it IS in fact at the end of the tape!

Here is my correct (ignore the funny block in the Start state)

*** Question 2 ***