# Question regarding stack operation notation in PDA

I'm currently reading two books:

1. An Introduction to Formal Languages and Automata, 4th Edition by Peter Linz.
2. 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:

1. Peter Linz's solution:
2. 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:

-
I replaced your tag (pushdown-automaton) with (pushdown-automata) since the plural seems more appropriate. However, I'm a bit doubtful if such a tag is really needed. In fact, many of the tags you created in the last few hours, such as (context-free-grammars) and (pumping-lemma) are a bit on the too specific side for my taste. – t.b. Aug 22 '11 at 8:23
@Theo Buehler: The reason I added those tags is just because of clarity. More importantly, I want more student visit this site for Elementary Theory CS questions. I understand this is math forum, but to be honest I couldn't find anywhere else which fits these type of problems. The odd thing is cstheory doesn't allow these elementary questions. Finally, thanks for the tag correction. – Chan Aug 22 '11 at 9:52
Your questions are perfectly fine here in my opinion and I don't see them as off-topic at all! In fact, I think it would be great if there were more such questions, especially such carefully crafted ones as yours. I was merely making a comment expressing doubts concerning the necessity of these very specific tags. The tag (automata) is fine with me, but (pumping-lemma) seems too special. We don't have a tag (jensen-inequality) or (fundamental-theorem-of-calculus) either, even if their importance is comparable to (pumping-lemma). – t.b. Aug 22 '11 at 10:00

Thanks for your suggestion. I guess I should stick with both notation since I think looking at a problem from two different angles sometimes gain some insights. By the way, I've just realized, the solution given in Peter Linz's book is actually wrong, it must have another loop for state $q_0$ on input $a$ as well. – Chan Aug 22 '11 at 8:09