How can i draw a PDA which has only 2 states and accepts strings which have odd number of a and even number of b?

the alphabet is {a,b}, and the PDA has to be only 2 states?

  • $\begingroup$ You can do it with 2 parallel DFAs each with 2 states. Make the top of the stack represent one of the DFAs and the states of the PDA the other. $\endgroup$ – ratchet freak Sep 26 '17 at 13:48
  • $\begingroup$ Wow thats actually very smart, thanks for the answer, also one last question, can we have something inside our "stack" in the initial state before we get any input ? or the stack has to be always empty at the beginning ? @ratchet freak $\endgroup$ – Richard Jones Sep 26 '17 at 13:59
  • 1
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Sep 27 '17 at 0:55

I like to remind you that in fact for every context-free grammar there exists an equivalent PDA that has only a single state using acceptance by empty stack. If we need to use PDA acceptance by final state then two states are required as we need a working state and a separate accepting state.

The single state construction is given on wikipedia's page for PDA and is called the expand-match construction for "parsing" context-free languages. The state here is called $1$.

  1. $(1,\varepsilon ,A,1,\alpha )$ for each rule $\displaystyle A\to \alpha $ (expand)
  2. $\displaystyle (1,a,a,1,\varepsilon )$ for each terminal symbol $a$ (match)

Note this uses the classical definition of PDA where the automaton starts with a fixed single element on its stack. A certain textbook has decided to change this basic definition and starts with the empty stack, where an extra state is needed to push the initial stack symbol. (horrible, this textbook is actually quite common and continues to spoil young kids).

when restricted to FSA the construction is actually quite simple. The PDA keeps the state on the stack as its only element. Accepting states of the FSA may be popped from the PDA so the PDA can accept (by empty stack) whenever the FSA can accept.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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