Return to Video

01-52 Epsilon And Ambiguity

  • 0:00 - 0:03
    实际上,Python的正则表达式模块
  • 0:03 - 0:07
    在内部的操作跟FSM是很相似的
  • 0:07 - 0:09
    你只要把正则表达式
  • 0:09 - 0:12
    转换成有限状态机,这个你前前后后已经做了很多次咯
  • 0:12 - 0:17
    然后用一个简单的递归函数来检查
  • 0:17 - 0:20
    该有限状态机是否能接受一个字符串
  • 0:20 - 0:25
    可是,我们的模拟器处理不了epsilon 过渡或者歧义
  • 0:25 - 0:29
    我这里说的歧义,指的是如果有两条标示为a的边界,怎么办呢?
  • 0:29 - 0:32
    假设一条指向一个接受状态,另一条不是
  • 0:32 - 0:34
    我们应该怎么做呢?
  • 0:34 - 0:36
    对于这种类型的歧义,有一个正式的定义
  • 0:36 - 0:38
    可是,它不能解决我们的问题
  • 0:38 - 0:41
    我们看到一个有限状态机能接受一个字符串
  • 0:41 - 0:46
    如果沿着字符串s,有一条路线能从开始状态
  • 0:46 - 0:49
    移到任意的接受状态
  • 0:49 - 0:52
    这个有限状态机能接受a
  • 0:52 - 0:55
    因为a能在
  • 0:55 - 0:57
    接受状态结束
  • 0:57 - 1:00
    如果你喜欢,你可以说有限状态机是"大方"的
  • 1:00 - 1:03
    如果有任意的方法能接受,它都能起作用
  • 1:03 - 1:06
    可是,我们的有限状态机模拟器
  • 1:06 - 1:08
    不能完全实现这点,所以我们必须要回到
  • 1:08 -
    所有的这些问题上
Title:
01-52 Epsilon And Ambiguity
Description:

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

Chinese, Simplified subtitles

Revisions