Return to Video

01-49 More FSM Encoding

  • 0:00 - 0:05
    Well, once again, I recommend getting started by drawing the finite state machine.
  • 0:05 - 0:09
    So on a or on b, we go over to state 2,
  • 0:09 - 0:11
    and we could end there because this is optional,
  • 0:11 - 0:16
    or on c or d, we could go to state 3 and end there.
  • 0:16 - 0:22
    Here at the top, I've encoded the edges from state 1 on a we go to state 2.
  • 0:22 - 0:25
    From state 1 on b, we go to state 2 as well--a or b.
  • 0:25 - 0:28
    From state 2 on c, we go to state 3.
  • 0:28 - 0:31
    From state 2 on d, we go to state 3.
  • 0:31 - 0:33
    And both states, 2 and 3, are accepting.
  • 0:33 - 0:36
    Then down here, I have 3 test cases.
  • 0:36 - 0:39
    "ac" which should be accepted.
  • 0:39 - 0:42
    "aX" which should not. X has no business in this regular expression.
  • 0:42 - 0:47
    And just "b" alone, which should be fine because the c - d part is optional.
  • 0:47 - 0:48
    Let's go see.
  • 0:48 - 0:51
    And we get exactly the output we were expecting--true, false, true.
  • 0:51 - 0:57
    Now you might have been tempted to have a c - d self-loop back to 2,
  • 0:57 - 1:00
    instead of this right-hand side of the finite state machine.
  • 1:00 - 1:05
    However, this self-loop changes the meaning to "[a - b][c - d]*".
  • 1:05 - 1:11
    If you have this self-loop, acc is accepted--a-c-c, and it shouldn't be,
  • 1:11 -
    so the self-loop is not the right way to go.
Cím:
01-49 More FSM Encoding
Leírás:

more » « less
Video Language:
English
Team:
Udacity
Projekt:
CS262 - Programming Languages
Duration:
01:15
Amara Bot hozzáadott egy fordítást

English subtitles

Felülvizsgálatok