[音乐] 嗨,欢迎回来。
我们这一节呢我们再谈一谈如何来实现这个有限状态机。
既然我们有计算机这么强大的工具哦,肯定能用它来实现 稍显简单一些的有限状态机。
实际上呢我们用程序设计语言 可以很容易地实现有限状态机。
那么有限状态机既然是状态,既然状态机了,有状态的
变来变去,而且我们也提到这个状态呢是属于机器里头的一个内部的记忆,
OK,我们就用一个变量来记录这个状态,我们定义这个变量 status
, 然后把这个 s0 赋给它,将来呢所有的这个状态呢都记在这个变量里。
好,接下来呢就是对于这个读入字符和状态转移函数的 一个实现了。
那么读入字符我们就用这个类似于 C 语言的代码
while ( a = get_next_input () ),就是得到下一个字符。
只要这个还有字符,那么就做中间的这个循环体, 这个循环体呢就是状态转移函数。
那么对于这个 状态转移函数呢就是基于当前的这种状态,然后呢再判断 读入的字符是什么,然后转移到下一个状态。
所以我们用一个 switch 语句 来判断现在的状态是什么, switch ( status ) of {。
然后如果是 case 是 s0 的话,那么
再看看这个读入的字符是什么,switch ( a )。
如果读入字符是 x ,那么从 s0 转移到 s3 ,所以
status 就等于 s3 , 然后如果是代输出的话,那么就
output 一个输出,比如说 output ( '0' )。
那么这个状态转移的过程就停止了,状态转移了,然后也输出字符了,对吧。
如果是 读入一个 y ,那么它可能会转移到 s4 这个状态,然后输出一个 1 ,然后也 break ,也停止了。
那么假设呢这个 s0 这个分支它就是, 就说这个
A 这个字符集只有包含 x、 y 这两种字符,那好它这个分支就停了。
这是 s1 ,那对于 status 来说,还有 s1、 s2、 s3。
那么 s1 呢也是重复一个 switch (a) 多少, x
转移到什么状态,输出什么,对于读入 y ,状态转移到什么再输出什么。
那么这都是重复这样的过程,所以呢只要把 s0、 s1、 s2 它所有的
状态都用这个 case 语句都列出来,然后当中呢再嵌套一个
switch 语句来判断输入的这个字符是什么,然后分别呢给出它每一个输入字符的
这个状态转移的目标状态以及它的输出的字符, 就ok了。
那么只要有这么一个程序的这个框架、 这个样子, 我们整个呢就能够把这个有限状态机 给它给模拟出来。
那么当然这个书写的语言其实无所谓,你用 C 语言 写也可以,用Python
来写也可以,那么只要是这个算法语言,那么 它都有这样的机制,都是可以的,无非就是顺序循环和这个分支的
这种三个结构给它组合一下,那么很简单地就用这个可以构造出一个有限状态机来。
那么将来呢你如果在科研当中、 学习当中要用到这个
有限状态机的话,那么这个程序的框架大概就是这样的。
你如果有点记不住,你可以回头来看我们的这个视频和 PPT。
那么在最后结束的时候,它会返回一个结束的状态,可能输出呢该输出的都
已经在运行的过程当中输出了,最后呢最终停止的那个状态来一个 return
status 就可以知道它最终停在什么一个状态下,这就 OK 了。
接下来呢我们再来讲一讲关于有限状态机的一些有趣的一些事实。
那么首先呢,它的限制在哪? 我们说呢它状态输入是有限的,所以它做的事情呢可能也比较有限,
而且我们从iii里头也看出来,它所能够识别的这个 字符串的模式大概就是那个样子,中间呢能够,
只要有一串被识别了,那么中间的所有的这个不停的重复它都能够被识别。
那这个呢实际上就限制了这个字符的这种, 字符串或者语言的这种多样性,是吧。
那么 再进一步说,带操作的这种
字符的加法的模拟的这种 有限状态机,它实际上我们分析这个加法吧,
它实际上这个有限状态机只要,它的特点是只要说输入 字符停止了,输入完了,那么它输出就必须停止。
所以呢对加法来讲,这问题不大。
因为两个数加呢, 它最多呢在最大的那个数上会有一个进位, 只有一位而已。
所以呢我们用了一个小技巧, 算是一个输入终止符号的一个
B ,实际上呢这是为了充数用的,
就是为了这个进位的这么多一位出来, 但是因为 B 输入完了以后马上就不会再有输入了。
所以呢对于那些相对于输入而言,输出它会有
增长的情况,那有限状态机 它就没法处理了。
比如说它就不能够说做这种操作位数没有限制的这种
二进制的乘法,那么它就没有办法用有限状态机来去做它。
那么而我们说现实当中的这个计算机,它虽然,
我们后面会谈到它的这个理论模型是图灵机,按理说它的能力应该会
要比有限状态机要强得多,但是实际上现实当中的计算机 它的内存是终归还是有限的,
那我们知道只要内存有限,它实际上它所能表达的这个状态的组合,
状态其实也是有限的,最终呢它实际上它也还是属于这种有限状态机,只不过说
它可以用这种有限状态机来模拟一定程度的 这种图灵机的运行而已。
所以呢它能做 各种各样的这个运算,但是都是属于模拟的运算,
而且呢位数也是有限的,所以呢它能做乘法, 但是位数是有限的,那种无限多位的这种乘法
在现实当中的计算机当中还是没有办法去做。
接下来呢如果我们把这个有限状态机这个理论再扩展到哲学的领域哦,
也发现了一些很多有意思的事情。
如果说我们把宇宙看作是有限的, 然后很多人说,因为关于宇宙是有限或者无限的
这个争论也有,一些哲学家认为宇宙是无穷的, 它不会穷尽;也有人说呢认为说宇宙它,
它可能是有限但是没有边,它总的这个物质说呢还是有限的。
那如果是我们承认说有限的话,那么理论上来说 这个按照计算机器的模型来说,这个宇宙呢
也是一个有限状态机,只不过这个状态呢 非常非常非常的大而已,但是再大它也是有限的,对吧?
那么这个我们就可以得出一个结果,只要经过有足够长的 时间,因为这个宇宙也是在进行演变的过程,它也
是在做状态转移嘛,对吧?状态转移函数。
从一个状态转到另一个状态而已。
那么只要经过足够长的时间,当然这个时间特别特别的长啊,但是总是有限的。
它总会回到以前的某个状态。
这个我们跟那个iii所用的这个鸽笼原理是一样的。
你一个状态的序列,只要那个序列足够长,长到了超过了状态的数目以后,
这个中间肯定会有两个相同的状态,那么所谓的相同状态是什么呢?
就是从哲学上来说,就是历史还会重演的,对吧。
所以这个呢是整个呢是循环宇宙论的主要的论据。
所以我们通过学习离散数学, 通过学习有限状态机,实际上可以对于一些哲学命题
也能够有一个进一步的深入的认识,而为什么有,比如说佛教说
这个宇宙发展是循环的,到了一定的时候又会从头来过,
一切就又归零,然后又从头来过,然后发展了一段时间以后又归零从头来过,
那实际上它就是把整个宇宙看作是一个有限状态机,对不对啊?