- #1
Trentonx
- 39
- 0
Homework Statement
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
Homework Equations
NA
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?