Results 1 to 4 of 4

Math Help - Show that every finite automaton is a one-state pushdown automaton

  1. #1
    Newbie
    Joined
    Nov 2012
    From
    United States
    Posts
    2

    Show that every finite automaton is a one-state pushdown automaton

    I need help with Showing that every finite automaton is a one-state pushdown automaton

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    Re: Show that every finite automaton is a one-state pushdown automaton

    The best place for such questions is the Discrete Math subforum.

    Strictly speaking, a finite automaton is not a pushdown automaton because it does not have a stack. You probably need to emulate a finite automaton with a one-state pushdown automaton. What do you think about having a single symbol in the stack that represents the state of the finite automaton?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2012
    From
    United States
    Posts
    2

    Re: Show that every finite automaton is a one-state pushdown automaton

    Thanks for the reply
    But what if the finite automaton has more than one state? what about accepting state?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    Re: Show that every finite automaton is a one-state pushdown automaton

    Quote Originally Posted by user30669 View Post
    But what if the finite automaton has more than one state? what about accepting state?
    My suggestion addresses both of these issues. I suggested storing the state of the finite automaton in the stack.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. please help with this Q...... of Finite automaton
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 11th 2010, 10:21 PM
  2. finite Automaton
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 11th 2010, 09:25 PM
  3. Discrete Finite Automaton and the pumping lemma
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 24th 2009, 04:39 AM
  4. finite automaton proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 20th 2008, 02:35 PM
  5. finite state machines
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 9th 2006, 10:03 AM

Search Tags


/mathhelpforum @mathhelpforum