English subtitles

← 01-52 Epsilon And Ambiguity

Get Embed Code
5 Languages

Showing Revision 1 created 04/24/2012 by Amara Bot.

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