I'm currently reading two books:
- An Introduction to Formal Languages and Automata, 4th Edition by Peter Linz.
- Introduction to the Theory of Computation, 2nd Edition by Michael Sipser.
What confused me is the notations are used in these two books are very different from each other. For example,
Let $L = \{a^nb^{2n} : n \geq 0\}$
The solution to this PDA is straightforward:
- If we read an $a$, push two markers (or stack symbol) onto the stack.
- If we read a $b$, pop one marker (or stack symbol) out of the stack.
Now, let's draw the actual PDA:
- Peter Linz's solution:
- Michael Sipser's solution:
There are several differences that I've noticed:
- With Peter Linz's stack mechanism, we can actually push 2 symbols onto the stack at a time as opposed to Michael Sipser's one, we can only push 1 symbol onto the stack at a time.
- Peter Linz's solution also takes the top of the stack into account each time it performs a push. For example, the transition from $q_0$ to $q_1$: $a, z \rightarrow 11z$ $a, 1 \rightarrow 111$ Here, the PDA pushes two 1's onto a stack each time it reads an $a$, but it also looks at what symbol is currently on the top of the stack. The string $11z$ for instance means top $\rightarrow$ bottom and is read from left to right. While Micheal Sipser's solution doesn't really care about the top stack symbol. As long as it reads an $a$, it pushes a $x$ onto the stack. More specifically, the notation $a, b \rightarrow c$ means
- read a, if $a = \lambda$, read nothing.
- pop b, if $b = \lambda$, pop nothing.
- push c, if $c = \lambda$, push nothing.
I personally prefer Michael Sipser's notation over Peter Linz's one because I think it's not necessary to keep track of which symbol is currently on the stack. Unless there is a case when this extra step matters, otherwise I feel it's quite trivial to express the transition function in Michael Sipser's way. Besides, I wonder if "is it correct" to allow pushing "2" symbols at a time onto stack? Plus, among these two methods, which one is more standard and more widely used?
Update Correct PDA of Peter Linz's solution: