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

Can someone help me construct a pushdown automaton to recognize the following regular expression representing the language $(a^3+a^5)$* using as few states as possible? How can this be done using a stack?

share|cite|improve this question
Is that a regular expression for the language? – Dustan Levenstein May 30 '12 at 12:08
Yes, thank you! – Jack Kobil May 30 '12 at 12:08
You can do it with an empty stack ... – Monoide May 30 '12 at 12:20
I see how this can be done using a finite automaton but not sure how to implement it with a pushdown automaton. – Jack Kobil May 30 '12 at 12:36
because it's a regular language, you can just write a finite automaton which accepts it, and that is the same as a pushdown automaton which doesn't use the stack. But if you want to minimize the number of states, you have to use the stack. – Dustan Levenstein May 30 '12 at 12:37

You can do it with a single state -- just shove the states of the obvious no-stack finite automaton into the stack alphabet and use the first element of the stack to remember the state. You then never need a stack depth of more than one.

(Of course this is subject to the details of how you formalize PDA's. If your formalization don't allow you to pop a symbol off the stack and push a new one onto it in the same transition, then this construction won't help).

share|cite|improve this answer

Hint (assuming this might be homework -- please tell us if not) -- think of how you'd recognize, say $(a^k)^*$ for a fixed $k$ (try $k=2, 3, 4 \text{ or } 5$) using a single state and a pushdown store, with acceptance by empty stack. Now, how can you pick $k$ and combine that with a finite-state automaton a having minimal number of states to recognize the language in question?

share|cite|improve this answer

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.