1
$\begingroup$

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.

  • 0
    There is some discussion on Meta about the new tags you've recently created. You may want to comment upon it.http://meta.math.stackexchange.com/questions/2466/new-tags-when2011-08-22
  • 0
    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.2011-08-22

1 Answers 1

2

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,\$$?)

  • 0
    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.2011-08-22