1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Help understanding Non-determinate Finite Automaton

  1. Feb 23, 2015 #1
    1. The problem statement, all variables and given/known data
    There's not a particular problem, per se, just that I seem to be missing something with my understanding of how to evaluate a string against a non-deterministic finite automaton with epsilon transitions. But one I've been working with is shown below


    2. Relevant equations

    3. The attempt at a solution
    I'm told by my professor this represents the regular expression a*b*c*. As such, I wouldn't expect the machine to match on an input string of "cb". But from my understanding, it does. You can see in the image my attempt at the states the machine would enter, given each input token. And after, the machine is in at least one goal state, so it matches. But I wouldn't expect the string "cb" to match a*b*c*

    It's pretty clear I don't understand how to handle the epsilon transitions. Do I follow them to all the way, as I did above? Only follow epsilons from the current state to at most one "hop" away? Should I somehow evaluate epsilons before hand, then token and more epsilons? Are epsilons filtered somehow?
  2. jcsd
  3. Feb 23, 2015 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    Your interpretation seems to be that if a state cannot accept a symbol then an epsilon transition occurs. I think epsilon transitions occur without any symbol being accepted. An epsilon transition "activates" a state for the purpose of accepting symbols. Initially, the automata has states 1,2,3 active. Only state 3 can accept the "c". The "c" "blocks" states 1 and 2 so they become inactive. So after "c" is accepted, the only active state is state 3. State 3 cannot accept the "b".

    If state 3 had a epsilon transistion going back to state 2 then the "b" could be accepted by state 2. However I interpret the diagram to say that epsilon transition from 2 to 3 is one-way.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted