Automata? NFA, DFA, PDA

v2sam 发表于 2018-5-23 10:53
那么，自动机是啥？？？？

自动机就是一个抽象的机器，可以用来研究可计算性问题。
而且自动机有好多种，它们的限制条件不同，适用的范围也不同（可以识别不同的语言，换句话说你给它编程的自由度不同）
举个简单的例子，有限状态自动机，对应乔姆斯基3型文法，可以识别正则语言（“正则表达式”听说过？它是一种已经规范化的成为业界标准的正则语言，尽管有许多变种）
一个确定性有限状态自动机可以描述为一个五元组(Σ,S,s0,δ,F)

这个机器可以吸进去一个有限长的纸带，然后纸带上划分好格子（一维的），每个格子上可以有一个字母，所有能用的字母构成的集合是Σ。
这个机器还能有一个状态，这个状态的所有可能取值是集合S。
机器启动的时候初始状态是s0
然后机器就一格一格地按照顺序往下读取这个纸带上的字母，设读到的字母是s
δ是状态转移函数，按照C++的话说就是
S δ(S current_state, Σ current_alphabet) {
  //根据当前状态+当前字母，转移到一个新的状态
  S new_state;
  return new_state;
}
最后F是一个集合，它是S的子集，表示终止状态

然后这个抽象机器可以干嘛呢？

比如你要识别某个字符串是否满足特定的规则。

它由任意个0或者1组成，并且不能包含两个或以上相邻的00。
这个有限状态自动机也能处理。一开始是q0，读到一个0就进入q1，再读到0就进入qt了。当状态为qt的时候不管读到什么都在qt里打转出不去了，并且qt不在F里面（q0和q1在）。假设我们输入“01001”，这个自动机读完纸带最终进入qt，我们就不接受这个输入。
再想想正则表达式，是不是有点这个味道了？实际上正则引擎把你输入的正则表达式变换为等价的自动机，然后用它去识别一个字符串，看它是不是自己接受的语言。

当然也有更复杂的自动机，能识别的语言更复杂，状态转移函数也更复杂。比如图灵机好像有一个可以左右来回移动的读写头，不光可以读取纸带上的字母还能把当前格子替换为其他字母…具体数学定义我就不写了，它可以搞定乔姆斯基0型文法（识别短语结构语言）

其实自动机这东西就是个数学描述而已。比如图灵机它的纸带是无限长的，而实际计算机的RAM是有限的；比如图灵机只能一个一个格子地移动读写头，但我们的RAM是可以随机存取的……

你电脑里的CPU不是个自动机么）

自动机和元胞自动机有啥区别？

那么，自动机是啥？？？？