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?
Pushdown Automaton
-
0Is that a regular expression for the language? – 2012-05-30
-
0Yes, thank you! – 2012-05-30
-
3You can do it with an empty stack ... – 2012-05-30
-
0@Monoide can you elaborate further on this? – 2012-05-30
-
1I see how this can be done using a finite automaton but not sure how to implement it with a pushdown automaton. – 2012-05-30
-
2because 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. – 2012-05-30
-
0I can't see what could be pushed and popped from the stack to help minimize the number of states. – 2012-05-30
-
0The trouble for us is that there are many definitions of a pushdown automaton. Any chance you could point to a reference explaining exactly which definition you're using? – 2012-05-30
-
0I've googled it, it's pretty much the standard nondeterministic pushdown automaton defined by wikipedia. – 2012-05-30
-
0@JackKobil sorry, I didn't realize that you had responded until now. The software doesn't give a notification unless you tag the person you're responding to. In any case, you can work off of David's answer and ask any followup questions to his answer. – 2012-05-30
2 Answers
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).
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?