How do you obtain transition relation of a PDA?

Question

I know how to figure out the start state, accepting state, input alphabet, and all that stuff. But how do you develop thetransition relation of a PDA? For an FSM, (q0,a),q1) means if you start at q0 and get an a, you transition to q1. But what does (S,a,e),(S,a) mean? (S is start state and e is epsilon)

Answer 1

Instead of an epsilon in (S,a,e),(S,a) that should be a bottom symbol (looks like an upside-down T). I'll explain this a little later.

The first S is simply what state you're in now. This corresponds to the q0 in the FSM.

The a is the symbol that you read, the same as the a in the FSM. Note that when you get an e instead of the a that means you're at the end of your string, there's nothing left to read.

The main difference is with the next letter, in this case an e. This denotes the single stack symbol that's on the top of the stack when you read your a. Technically you can never read an empty stack though. In computers this is the same as reading null memory, it just can't be done. This is because the "bottom" of the stack contains a single symbol that says that you're at the bottom. Traditionally this is expressed using an upside-down T (the bottom symbol).

The S in the second bracket denotes the state that you're going to, just like the q1 in the FSM.

Finally, the a in the second bracket is what symbol (or symbols) you want to add onto the stack. Every time you read something from the stack (which is every time a transition occurs), that symbol is removed from the stack. Then, you can put a new symbol or several new symbols onto the stack, or you can put nothing (e). Putting nothing on when you've just read the bottom symbol means that you're done, and you're accepting the string (if accepting by empty stack). You can also accept by final state, but empty stack is a little simpler.

I'll show you a quick example, a PDA for {a^n b^n | n >= 0}. Our alphabet is evidently {a,b}, we'll need 2 states (one for the a section and one for the b section), let's call them {p,q}. We'll let p be our start state. Our stack alphabet, the symbols we can put onto the stack will be {bottom,A}. Bottom is always a part of the stack alphabet, and we'll push an A onto the stack every time we get an a (and pop one every time we get a b). Let's accept by empty stack, which means when we read e as the symbol and bottom as the stack symbol, if we put nothing back on the stack then we have accepted that string. Our delta transitions are as follows:

(p,e,bottom),(p,e) //this is an accepting state for a^0 b^0
(p,a,bottom),(p,A bottom) //we read an a and we're at the bottom of the stack, we add an A to the stack and put back the bottom symbol below it.
(p,a,A),(p,AA) //we read an A off the stack and an *a* in our string, we put back the A we read from the stack and add another one
(p,b,A),(q,e) //we read an A off the stack and a *b*, so we go to our state q, and don't add anything to the stack.
(q,b,A),(q,e) //every time we get a *b* and there's an A on the stack, remove it
(q,e,bottom),(q,e) //this is an accepting state, as we've canceled out all the a's with b's and we're done reading our string.

Note that there are transitions that aren't allowed, such as getting a b before any a's. By not including them, strings that require them are not accepted. Hope this helps!