# How to build a PDA that accepts strings which have odd numbers of a and even numbers of b and has only 2 states?

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?

• 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. – ratchet freak Sep 26 '17 at 13:48
• 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 – Richard Jones Sep 26 '17 at 13:59
• 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. – D.W. Sep 27 '17 at 0:55

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)