# Question regarding the initial stack symbol in Push Down Automaton

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: 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. - There is some discussion on Meta about the new tags you've recently created. You may want to comment upon it.meta.math.stackexchange.com/questions/2466/new-tags-when – 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 ## 1 Answer 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,\?)

-
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