跳转至

有穷自动机

https://blog.csdn.net/jzyhywxz/article/details/78307168

https://blog.csdn.net/jzyhywxz/article/details/78300350

有穷自动机

不确定的有穷自动机 NFA

一个不确定的有穷自动机(Nondeterministic Finite Automate,下文简称NFA)由以下部分组成:

结点集合:一个有穷的状态集合S; 标记集合:一个输入符号集合∑,以及空串ε; 转换函数:它为每个状态和∑∪{ε}中的每个符号都给出了相应的后继状态的集合。即转换函数的输入是某个状态s和∑∪{ε}中的某个符号a,输出是从状态s出发,经过标记为a的边,能够到达的所有状态的集合; 初始状态:S的一个状态被指定为初始状态; 终止状态:S的一个子集被指定为终止状态的集合。

确定的有穷自动机 DFA

确定的有穷自动机(Deterministic Finite Automate,下文简称DFA)是NFA的一个特例,其中:

标记集合:一个输入符号集合∑,但不包含空串ε; 转换函数:对每个状态s和每个输入符号a,有且仅有一条标号为a的边离开s,即转换函数的对应关系从一对多变为了一对一。