Return to Video

01-52 Epsilon And Ambiguity

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

more » « less
Video Language:
English
Team:
Udacity
Project:
CS262 - Programming Languages
Duration:
01:11
Amara Bot added a translation

English subtitles

Revisions