Return to Video

01-57 Nondeterminism

  • 0:00 - 0:04
    这些容易编写的有限状态机,我们已经在使用
  • 0:04 - 0:07
    包含epsilon 转换或者歧义
  • 0:07 - 0:11
    记住,歧义表示对于同一个输入我可以去两个不同的地方
  • 0:11 - 0:16
    正式来说,被称作非确定性有限状态机
  • 0:16 - 0:19
    这里的非确定性只是意味着你可能不是明确地知道
  • 0:19 - 0:21
    要去哪里或者把你的手指放在哪里
  • 0:21 - 0:24
    这不是锁死的,你可以做选择
  • 0:24 - 0:26
    你能自由地选择
  • 0:26 - 0:29
    相反,没有epsilon转换和没有歧义
  • 0:29 - 0:34
    的锁死的FSM被称为确定性有限状态机
  • 0:34 - 0:36
    一切从一开始就决定了
  • 0:36 - 0:38
    已知有限状态机和输入,你总会明确知道
  • 0:38 - 0:40
    将要发生的事情
  • 0:40 - 0:43
    我们的有限状态机模拟函数能够处理
  • 0:43 - 0:46
    确定性有限状态机
  • 0:46 - 0:49
    这使它们对于实现正则表达式
  • 0:49 - 0:51
    真的很有用
  • 0:51 - 0:55
    让我给你们看一个非确定性有限状态机的例子
  • 0:55 - 0:57
    假设我们回到这前一个有限状态机
  • 0:57 - 1:00
    但是现在输入的是1-23
  • 1:00 - 1:02
    我们在哪里?
  • 1:02 - 1:05
    我们从这里开始,遇到1,我们移到这里
  • 1:05 - 1:08
    我想如果我们应该还“活着”,且遇到了连字符
  • 1:08 - 1:11
    我们必须来到这里接受这连字符
  • 1:11 - 1:14
    接着是2,但现在这真的不明显
  • 1:14 - 1:17
    因为到了3,我可以自循环回这里
  • 1:17 - 1:20
    或者我可能回到这个epsilon转换
  • 1:20 - 1:25
    并且在遇到3时,结束这个自循环,所以我可以在状2或者状态5
  • 1:25 - 1:28
    因为我可以得到不止一个答案
  • 1:28 - 1:30
    这就是非确定性
  • 1:30 - 1:34
    除了有点有趣之外,确定性和非确定性
  • 1:34 - 1:39
    的概念与哲学上关于自由的问题联系起来
  • 1:39 - 1:42
    我们真的可以做独立的选择吗?
  • 1:42 - 1:45
    或者说是不是一切都是由世界的当前状态和强加于其上的力量
  • 1:45 - 1:51
    注定的,就好像是一场注定结果的桌球游戏那样?
  • 1:51 - 1:53
    一些哲学家声称我们有着对自由意志的幻想
  • 1:53 - 1:57
    --这是一种令人不安的想法--
  • 1:57 - 2:00
    这种幻想能方便地描述主观的体验
  • 2:00 - 2:02
    我们肯定经常感觉我们有着自由意志
  • 2:02 - 2:05
    无论在真实世界里发生什么事情
  • 2:05 - 2:07
    我们将会看到一些类似的东西对
  • 2:07 - 2:09
    有限状态机也适用
  • 2:09 - 2:12
    尽管非确定性有限状态机看起来
  • 2:12 - 2:14
    有着更多的力量和更多的自由
  • 2:14 - 2:17
    但是任何能用它们完成的事情,也可以
  • 2:17 - 2:19
    在我们的确定性有限状态机来实现
  • 2:19 - 2:23
    In fact, you can watch me suck free will out of this world right now.
  • 2:23 - 2:26
    每一个非确定性有限状态机
  • 2:26 - 2:29
    都有着对应的确定性有限状态机
  • 2:29 - 2:33
    来接受完全一样的字符串
  • 2:33 - 2:37
    非确定性有限状态机不比
  • 2:37 - 2:39
    确定性有限状态机强大多少
  • 2:39 - 2:42
    它们 只是更加方便罢了
  • 2:42 - 2:44
    编写它们更加容易
  • 2:44 - 2:46
    让我来看一个关于这个特别声明的例子
  • 2:46 - 2:48
    假设我们有这个正则表达式
  • 2:48 - 2:51
    在这个正则表达式里只有两个字符串
  • 2:51 - 2:55
    但这里我画出了对应它的一个非常复杂的有限状态机
  • 2:55 - 2:57
    有着epsilon转换
  • 2:57 - 3:00
    这是非确定性的
  • 3:00 - 3:03
    我们肯定需要看到a,但这里这两个epsilon转换
  • 3:03 - 3:05
    代表明确的选择
  • 3:05 - 3:08
    我要选择b,还是要跳过它呢?
  • 3:08 - 3:10
    在上面的路线,我们需要看到b
  • 3:10 - 3:13
    在下面的路线,我们完全跳过它
  • 3:13 - 3:15
    接着无论怎样,我们需要看到c
  • 3:15 - 3:19
    现在我将画出一个确定性有限状态机
  • 3:19 - 3:22
    它能实现完全一样的功能,我将提到
  • 3:22 - 3:24
    这个转换是怎样进行的
  • 3:24 - 3:26
    我们将很快看到这个
  • 3:26 - 3:29
    在看到a之后,我可以在状态2
  • 3:29 - 3:31
    或者我执行epsilon转换,移到状态3
  • 3:31 - 3:33
    我可以执行epsilon转换而来到状态6
  • 3:33 - 3:36
    或者一直到状态4,所以我可以处在
  • 3:36 - 3:38
    4个状态里
  • 3:38 - 3:40
    那真的是很多”手指“
  • 3:40 - 3:44
    我只要将他们记下为我的新状态,2364
  • 3:44 - 3:49
    这里,如果我看到了b,那就能”活下“了 -- 记住,如果有着任意路线
  • 3:49 - 3:54
    能去到结尾,那么这个有限状态机就起作用,我之前一定在状态3
  • 3:54 - 3:57
    现在我就在状态4
  • 3:57 - 4:03
    相反,如果我返回这里,我看到c
  • 4:03 - 4:06
    那一定是我之前在状态4,现在我到了状态5
  • 4:06 - 4:10
    最后,如果我在状态4,我看到c
  • 4:10 - 4:13
    那就在这结束了,所以这个确定性有限状态机
  • 4:13 - 4:17
    能像上面那个一样接受同样的字符串
  • 4:17 - 4:20
    这两个字符串,abc和ac
  • 4:20 - 4:23
    都在它里面,但是它没有
  • 4:23 - 4:25
    epsilon转换或者歧义
  • 4:25 - 4:29
    在任意特定的节点里,不会有两条标示为a的流出的边界
  • 4:29 - 4:31
    也不会有epsilon转换
  • 4:31 - 4:34
    让我们来看看另一个例子
  • 4:34 - 4:37
    再一次,我将构造一个有限状态机
  • 4:37 - 4:40
    在这个有限状态机里的每一个状态
  • 4:40 - 4:44
    都对应于非确定性有限状态机的
  • 4:44 - 4:46
    一组状态
  • 4:46 - 4:50
    再次说明下,已知一个非确定性的状态及
  • 4:50 - 4:53
    我将构建一个能够接受同样语言的确定性有限状态机
  • 4:53 - 4:57
    而我实现的方法似乎
  • 4:57 - 5:01
    在d里每一个状态将对应于
  • 5:01 -
    非确定性状态机里的一组状态
Cím:
01-57 Nondeterminism
Leírás:

more » « less
Video Language:
English
Team:
Udacity
Projekt:
CS262 - Programming Languages
Duration:
05:05
hwingh edited Chinese, Simplified subtitles for 01-57 Nondeterminism
hwingh hozzáadott egy fordítást

Chinese, Simplified subtitles

Felülvizsgálatok Compare revisions