It turns out that Python's regular expression module
actually uses something very similar to FSM sim under the hood.
You just take the regular expression,
turn it into a finite-state machine, which you've done forwards and backwards
many times, and then check with a simple recursive procedure
to see if the finite-state machine accepts a string.
However, our simulation did not handle epsilon transitions or ambiguity,
and what I mean by ambiguity is what if there are 2 outgoing edges labeled a?
Let's say one of them leads to an accepting state, and one of them doesn't.
What should we do?
Well, there is a formal definition for this kind of ambiguity.
However, it's not going to solve our problems.
We see that a finite-state machine accepts a string s
if there exists even one path from the start state
to any accepting state that follows s.
This finite-state machine accepts a
because there's one way to do it where a causes you
to end up in an accepting state.
If you like, you can say that finite-state machines are generous.
If there's any way to accept, we will make that work.
However, our finite-state machine simulation
didn't code that up, so we're going to have to return
to both of these issues.