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

Let $L = \{a^nb^n : n \geq 0\} \cup \{a\}$, where $\Gamma = x, \$, \Sigma = {a, b}$, we have the NPDA of $L$ in three states:

enter image description here

In the above state diagram, I can break the transtion $\lambda, \lambda \rightarrow \$$ by creating another initial state, but my question is if I put it in the loop together is it still ok? Since the notation of Peter Linz's book is so confusing, I have to borrow Micheal Sipser's book notations for this problem. The idea of PDA is as follows:

  • Read nothing, push $ onto stack
  • Read an $a$, push $x$ onto stack.
  • Read a $b$, pop $x$ out of stack.
  • Special case is when reading an $a$, push \$ onto stack and move to state $q_1$, then from $q_1$ read nothing, pop \$ out of stack and go to accepting state.

Does this PDA looks reasonable at all?
Thank you.

share|cite|improve this question
There is some discussion on Meta about the new tags you've recently created. You may want to comment upon – Willie Wong Aug 22 '11 at 13:17
I apologize for not having notified you of the discussion @Willie refers you to. It wasn't specifically about your tags and it isn't your fault. These tags just served as an illustration for my actual question: what to do with too-specific tags. It definitely wasn't the proper to do this without notifying you. Once again, my apologies for that. – t.b. Aug 22 '11 at 19:18
up vote 2 down vote accepted

Couldn’t your NDPA erroneously accept $aab$ by the following sequence?

  1. read $a$ and push $x$ onto the stack;
  2. read nothing and push $\$$;
  3. read $a$ and push $x$;
  4. read nothing and transfer to state $q_1$;
  5. read $b$ and pop $x$;
  6. read nothing, pop $\$$, and transfer to state $q_2$.

(By the way, shouldn’t the bottom label be $a,\lambda\to\$$, not $a,\lambda,\$$?)

share|cite|improve this answer
Ah ha, thanks for pointing that out. I should realize that I need an counter example ;). About the label, it was my typo. Thanks again. – Chan Aug 22 '11 at 2:54

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.