# Homework Help: Help understanding Non-determinate Finite Automaton

Tags:
1. Feb 23, 2015

### Trentonx

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
NA

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. Feb 23, 2015

### Stephen Tashi

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.