MORE on PDA's

Consider: we will now define an instantaneous description (ID) for a PDA, 
so that we can more easily show its operation (or, in this case, show 
that we understand the operation of a given PDA).

The current state of a PDA could be given as:
	(current state, remaining input to be handled, stack contents)
where
	remaining input's first symbol is assumed to be the one currently 
	being "pointed" at, 
and
	stack contents are assumed to be written so stack top is on the left;

You could then "trace" the action of a PDA as a series of ID's in this 
form, say separated by |--, as so:

FIRST: Consider the PDA M discussed in Sipser and in lecture: 
(d is used for delta throughout,
 e is used for epsilon throughout,
 and E might be used for sigma...)

M = ({q1, q2, q3, q4}, {0, 1}, {$, 0, 1},  d, q1, {q4}) where
d is defined as follows:
	d(q1, e, e) --> { (q2, $) }
	d(q2, 0, e) --> { (q2, 0) }
	d(q2, 1, 0) --> { (q3, e) }
	d(q3, 1, 0) --> { (q3, e) }
	d(q3, e, $) --> { (q4, e) }
 	(...and all others are undefined)

So, let's consider the operation of this PDA on the string 000111, using 
PDA ID's.

initial ID:	(q1, 000111, empty)

(q1, 000111, empty) |-- (q2, 000111, $)	(in state q1, without seeing an 
					input, push a $
					onto the stack without first popping the 
					stack) 
					(in state q2, when input 
					0, push a 0 onto 
					stack without first popping the stack)
                    |-- (q2, 00111, 0$)	(in state q2, 
					when input 0, push a 0 onto 
					stack without first popping the stack)
                    |-- (q2, 0111, 00$)	(ditto)
                    |-- (q2, 111, 000$)	(in state q2, 
					when input 1, when pop the 
					stack and see a 0 --- go to state q3 and
					do not push onto the stack
                    |-- (q3, 11, 00$)	(in state 
					q3, when input 1, when pop the 
					stack and see a 0 --- stay in state q3 and do 
					not do not push onto the stack

                    |-- (q3, 1, 0$)	(in state 
					q3, when input 1, when pop the 
					stack and see a 0 --- stay in state q3 and do 
					not do not push onto the stack
                    |-- (q3, empty, $)	(in state q3, 
					without seeing any input, when 
					pop the stack and see a $ --- go to state q4 
					and don't push anything onto the stack
                    |-- (q4, empty, empty)
...and, since we have exhausted all the input and are in a final state, 
the string 000111 has been accepted by this PDA M.    

SECOND EXAMPLE:
Consider the language {wc(w^R) | w is in (0 + 1)*}. Here is a PDA that 
accepts it:

M = ({q0, preC, postC, q3}, {0, 1, c}, {$, 0, 1, c},  d, q0, {q3}) where
d is defined as follows:

	d(q0, e, e) --> { (preC, $) }
	d(preC, 0, e) --> { (preC, 0)}	 
	d(preC, 1, e) --> { (preC, 1)}	 
	d(preC, c, e) --> { (postC, e )}	 

	d(postC, 0, 0) --> { (postC, e )} 
	d(postC, 1, 1) --> { (postC, e )} 
	d(postC, e, $) --> { (p3, e )}	

Consider the PDA ID's as this PDA processes the string 110c011:

(q0, 110c011, empty)	|-- (preC, 110c011, $)	|-- (preC, 10c011, 1$)	|-- (preC, 0c011, 11$)
			|-- (preC, c011, 011$)	|-- (postC, 011, 011$)	|-- (postC, 11, 11$)
			|-- (postC, 1, 1$)	|-- (postC, empty, $)	|-- (p3, empty, empty)
...and, since we have exhausted all the input and are in a final state, 
the string 110c011 has been accepted by this PDA M.
	
WHAT might I ask on a test in this area?
*   I might give a formal description of a PDA, and ask for a series of 
PDA ID's showing that some string is or is not accepted (to see if you 
understand PDA operation);
*   I might give a formal description of a PDA, and an ID for some point 
in the processing of a string, and ask for the ID that would next result 
(to see if you understand PDA operation);