
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 finitestate machine, which you've done forwards and backwards

many times, and then check with a simple recursive procedure

to see if the finitestate 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 finitestate machine accepts a string s

if there exists even one path from the start state

to any accepting state that follows s.

This finitestate 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 finitestate machines are generous.

If there's any way to accept, we will make that work.

However, our finitestate machine simulation

didn't code that up, so we're going to have to return

to both of these issues.