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