2006 Q6

Hi

This is my attampt at Question 6. I do believe it is correct, but you know what they say about assumption...

Question 6

(i) I will create a loop that push all the a(s) into stack 1 and stack to until a b is read.
Then I will push 3 extra a(s) into stack 1 and pop one a out of stack 2.
I will then for each a that is read pop a a from stack 1 until I read a b and then make sure stack 1 is empty.
I will then for each b that is read pop a a from stack 2 until I read a empty character and then also make sure stack 2 is empty.

(ii) Yes, because a PDA with 2 or more stacks can accept any language.

(iii) Yes, because a 2 stack pda is equivalent to a TM.

(iv) No, because a PDA can only accept context-free languages.

I did not check your i) answer, but I agree with your other answers.

A hint on iii): Check page 491 of Cohen, there is shows that nPDA = TM (n>=2). So you can actually say any nPDA = TM where n >= 2

_______________________________________
Don't be different...be the one making a difference

A good trick that's been used on some of the answers here is to invent a "Gamma" alphabet {x}

Now you push x's onto the stack.

Why?
It helps you keep the READ and the PUSH operations separate in your mind. The way we're using the stack at our level, all they do is count like tally sticks.

It's a slightly petty point, but remember that you are never taking the a you read from the Tape, and moving that selfsame a to the Stack. You read from the Tape. If its an a, you can branch on that, and that's all. The letter only tells you which branch to follow.

Now if along that branch you devise things such that you'll end up with a PUSH in your path, then (without regard to the letter that got you there) the machine will blindly push something onto the Stack.

Of course you can branch on POP, so you're not always putting mere tally sticks on the Stack ...

... but you can push anything. You can push X onto the stack if you reach it via an a-branch, for instance.

============== OK and now a bit on the actual question ==========

(i) Where will you get the a you want to pop from stack 2? (Maybe there are more questions one could ask here, but I'll just ask one).

(ii) 2PDA = TM = nPDA is a better answer, I think, but I reckon someone could come up with something yet better. .... Whoa ...

The way the next questions are framed that looks like it would not be the answer sought. I think what we'd need to do here is show how one could make Stack 3 such that it's guaranteed not to change anything.

Pause..

I have part of a 2PDA to do the job (will have to wing it at the end, since that's not on the notes).

At least one a, so we have a READ for that, leading to another READ. PUSH1x along the way. Crash for non-a.

Loop through PUSH1x on a, and branch out on b. This means we should have as many x as a on Stack1 by the end.

Now I look ahead and modify this a bit. Put in another push in that loop: PUSH2x. Again this is just a unary encoding of the number of a's initially received, minus one.

The b edge out of the second READ moves to a sequence of 3 "a-read". If a is read, move to next READ. That gives us the + 3 we'll need for the end of the second group of a's without using the stack. When we reach the third a we're on a loop to POP1.

If we pop a delta we go onward to a READ which loops serenely if it encounters a b on the tape, and crashes otherwise.

This final loop is on b, passing through POP2 each time. If a delta is popped from the Stack2 we check the Tape to see if it's at its end. So READ delta proceeds to HALT.

(I disregarded the instruction not to draw, and used a diagram as my "rough work".

Maybe we're meant to be more general when asked to "describe"?