1 Notation
Computing Theory
COSC 1107/1105
PDA and Turing machine notation
One often annoying feature of the material in this course is the different notations that occur. One example of this is in the use of different notations for transitions in PDAs and Turing Machines.
PDAs:
Consider a transition from state q0 to state q1 on input a, which takes B off the stack and pushes A onto it. This may be specified by any of the notations below above an arrow from q0 to q1.
a,B/A
a−B+A
The latter one has the advantage of being clear if there is no pop or no push involved, such as a+A or a−B. In the former case, one of the symbols needs to be the empty symbol, which is sometimes λ and sometimes ε.
Note that a transition labelled with a − ε + A does not mean that the stack has to be empty; just that there is no pop operation as part of this transition. For this reason it usually doesn’t make any sense to push (or pop) the empty symbol onto the stack. Stack elements must have content, if you like.
The key thing to remember, whatever the notation used, is that there needs to be five things specified: original state, new state, input symbol, what is popped, what is pushed. The latter three are generally in this order, if you have any doubt.
Turing machines:
Consider a transition from state q0 to state q1 on input a, which writes the blank symbol on the tape and moves left. This may be specified by any of the notations below above an arrow from q0 to q1.
aεL a/ε,L a/ε L
The key thing to remember, whatever the notation used, is that there needs to be five things specified: original state, new state, input symbol, output symbol, and direction to move. The latter three are generally in this order, if you have any doubt.