1
$\begingroup$

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?

  • 0
    Is that a regular expression for the language?2012-05-30
  • 0
    Yes, thank you!2012-05-30
  • 3
    You can do it with an empty stack ...2012-05-30
  • 0
    @Monoide can you elaborate further on this?2012-05-30
  • 1
    I see how this can be done using a finite automaton but not sure how to implement it with a pushdown automaton.2012-05-30
  • 2
    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.2012-05-30
  • 0
    I can't see what could be pushed and popped from the stack to help minimize the number of states.2012-05-30
  • 0
    The 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
  • 0
    I'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 2