六、 最优自动机
自动机性能 : 给定一个 自动机语言 A AA , 那么根据该语言可以设计出 不同的自动机 , 那么这些自动机之间的性能肯定是不同的 , 有的自动机性能高 , 有的自动机性能低 ;
最优自动机 : 从上述根据 同一个语言 设计出的多个自动机中 , 肯定能选出一个最优自动机 ;
七、 自动机设计算法
自动机生成算法 : 自动机是可以使用算法生成的 , 存在一种算法 , 用该算法生成一个 能识别给定语言的 最优的自动机 ;
八、 确定性 与 非确定性
1 . 确定性 思想 : 自然界一定是确定性的 , 给定一个输入 , 必定对应唯一一个输出 ; 如果出现非确定的输出 , 是由于人的认知有限 , 没有发现其中的未知变量 ; 随着科学认知的发展 , 这些不确定性会消除 ; 以牛顿力学为代表 ;
2 . 非确定性 思想 ( 主流 ) : 自然界是非确定的 , 一个输入对应 不确定 个输出 ; 以量子力学为代表 ;
确定性有穷自动机 的 确定性 , 就是上述确定性思想的应用 ;
下面要将 非确定性思想应用到 自动机设计中 ;
九、 自动机非确定性示例
上述 自动机 是一个非确定性自动机 , 非确定性主要体现在以下几个方面 ;
1 11 个字符输入对应 2 22 个输出 :
当前状态为 q 1 q_1q
1
时 , 读取字符 1 11 时 , 其后继状态有两个 , 既可以跳转到 q 1 q_1q
1
本身状态 , 又可以跳转到 q 2 q_2q
2
状态 ;
这个操作是一个非确定性的操作 , 读取一个字符 , 却对应了两个后继状态 ;
0 00 个字符输入对应 1 11 个输出 :
当前状态为 q 2 q_2q
2
时 , 读取字符 0 00 或者 ε \varepsilonε 空字符串 时 , 就可以跳转到 q 3 q_3q
3
状态 ;
ε \varepsilonε 表示空字符串 , 其类似于自然数中的 0 00 的概念 ;
0 00 个字符输入对应 0 00 个输出 :
当前状态为 q 3 q_3q
3
时 , 为其输入字符 0 00 , 其没有后继状态 ;
这个操作也是一个非确定性操作 , 读取一个字符 , 没有后继状态 ;
自动机中的不确定性 : 不确定性自动机中 , 允许 空字符 或 1 11 个字符 输入 , 对应 0 00 个 或 多个输出 ;
