有限自动机

有限自动机
有限自动机是一种具有有限个状态的转移系统，是最常用的语言和计算模型之一。
有限自动机的表示有五个要素。图2 是一个有限自动机 A 的转移图表示，我们以此为
例来说明这五个方面：
（1） 一个非空有限状态的集合。如，有限自动机 A 包含 q0，q1，q2 和 q3 等 4 个
状态，图中用圆圈表示。
（2） 一个非空的有限输入符号的集合。这相当于所代表语言的字母表。如，有限自
动机 A 的输入符号集合为 {0, 1}，这些符号出现在图中的转移边标记上。
（3） 一个转移函数。在转移图表示中，通过所有转移边来表示转移函数。如，有限
自动机 A 有 8 条转移边。对转移函数定义的不同限制，将导致不同类型的有
限自动机定义，我们随后讨论 3 种类型的有限自动机。
（4） 一个开始状态。在转移图表示中，我们用一个单箭头并标有 Start 来表示。如，
有限自动机 A 的开始状态为 q0。在有些文献和书籍中，有限自动机可以有不
止一个开始状态，但在本书规定只能有唯一的开始状态。
（5） 一个终态的集合。在转移图表示中，我们用双圆圈表示终态。如，有限自动机 A
有两个终态，q0 和 q3。