1 00:00:00,000 --> 00:00:03,000 It turns out that Python's regular expression module 2 00:00:03,000 --> 00:00:07,000 actually uses something very similar to FSM sim under the hood. 3 00:00:07,000 --> 00:00:09,000 You just take the regular expression, 4 00:00:09,000 --> 00:00:12,000 turn it into a finite-state machine, which you've done forwards and backwards 5 00:00:12,000 --> 00:00:17,000 many times, and then check with a simple recursive procedure 6 00:00:17,000 --> 00:00:20,000 to see if the finite-state machine accepts a string. 7 00:00:20,000 --> 00:00:25,000 However, our simulation did not handle epsilon transitions or ambiguity, 8 00:00:25,000 --> 00:00:29,000 and what I mean by ambiguity is what if there are 2 outgoing edges labeled a? 9 00:00:29,000 --> 00:00:32,000 Let's say one of them leads to an accepting state, and one of them doesn't. 10 00:00:32,000 --> 00:00:34,000 What should we do? 11 00:00:34,000 --> 00:00:36,000 Well, there is a formal definition for this kind of ambiguity. 12 00:00:36,000 --> 00:00:38,000 However, it's not going to solve our problems. 13 00:00:38,000 --> 00:00:41,000 We see that a finite-state machine accepts a string s 14 00:00:41,000 --> 00:00:46,000 if there exists even one path from the start state 15 00:00:46,000 --> 00:00:49,000 to any accepting state that follows s. 16 00:00:49,000 --> 00:00:52,000 This finite-state machine accepts a 17 00:00:52,000 --> 00:00:55,000 because there's one way to do it where a causes you 18 00:00:55,000 --> 00:00:57,000 to end up in an accepting state. 19 00:00:57,000 --> 00:01:00,000 If you like, you can say that finite-state machines are generous. 20 00:01:00,000 --> 00:01:03,000 If there's any way to accept, we will make that work. 21 00:01:03,000 --> 00:01:06,000 However, our finite-state machine simulation 22 00:01:06,000 --> 00:01:08,000 didn't code that up, so we're going to have to return 23 00:01:08,000 --> 99:59:59,999 to both of these issues.