Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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: enter image description here
  2. Michael Sipser's solution: enter image description here

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: enter image description here

share|cite|improve this question
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
up vote 4 down vote accepted

I think the main moral here should be it does not matter.

The two methods are evidently equivalent - pushing any given finite number of symbols at one time can be accomplished using a finite set of dedicated states. In general when discussing models of computation one must not lose itself in specific details of implementation as long as there is no serious difference between them (one example for such a difference: the number of states in a NDFA for a language can be exponentially smaller than the number of states in the best DFA for the language).

When you'll reach computability theory you'll see that this "freedom from specific implementation details" is truly crucial if you want to keep focusing on the important matters.

This is not a feature of theoretical computer science alone, of course; many mathematics books on diverse subjects use notation that can be quite different from one another. There is no universal rule as to what is correct; you should choose the notation you like best and stick to it.

share|cite|improve this answer
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

Later on in the book Sipser introduces a shorthand transition function which can pop the symbol at the top of the stack and push an entire string onto the stack at once. The function is of course defined using his original notation.

Say we want a transition of the form $(r,u) \in \delta(q,a,s)$, where $u$ is a string $u = u_1 u_2 \cdots u_l$.

We introduce new states, $q_1,q_2,\dots,q_{l-1}$, such that:

$\delta(q_1, \varepsilon, \varepsilon) = \{(q_2, u_{l-1})\}$

$\delta(q_2, \varepsilon, \varepsilon) = \{(q_3, u_{l-2})\}$


$\delta(q_{l-1}, \varepsilon, \varepsilon) = \{(r, u_1)\}$


$(q_1, u_l) \in \delta(q,a,s)$.

Judging by this, both Linz's and Sipser's are equally correct, with some problems being more suitable for one or the other. I personally prefer Linz's notation due to its terseness.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.