简述
有限自动机是一种状态机，它以一串符号作为输入并相应地改变其状态。有限自动机是正则表达式的识别器。当将正则表达式字符串输入有限自动机时，它会更改每个文字的状态。如果输入字符串被成功处理并且自动机达到其最终状态，则它被接受，即刚刚输入的字符串被认为是手头语言的有效标记。
有限自动机的数学模型包括：
- 有限状态集 (Q)
- 有限输入符号集 (Σ)
- 一个开始状态 (q0)
- 最终状态集 (qf)
- 过渡函数 (d)
转移函数 (δ) 将有限状态集 (Q) 映射到有限输入符号集 (Σ)，Q × Σ ➔ Q
有限自动机构造
令 L(r) 是某种有限自动机 (FA) 识别的常规语言。
-
States: FA 的状态用圆圈表示。州名写在圆圈内。
-
Start state：自动机开始的状态，称为开始状态。开始状态有一个指向它的箭头。
-
Intermediate states：所有中间状态至少有两个箭头；一个指着，另一个指着他们。
-
Final state：如果输入字符串被成功解析，自动机应该处于这种状态。最终状态由双圆圈表示。它可能有任何奇数个指向它的箭头和偶数个指向它的箭头。奇数箭头的数量比偶数大一，即odd = even+1.
-
Transition：从一种状态到另一种状态的转换发生在输入中找到所需符号时。转换后，自动机可以移动到下一个状态或保持在同一状态。从一种状态到另一种状态的移动显示为有向箭头，其中箭头指向目标状态。如果自动机保持相同的状态，则绘制一个从状态指向自身的箭头。
Example：我们假设 FA 接受任何以数字 1 结尾的三位二进制值。FA = {Q(q 0 , q f ), Σ(0,1), q 0 , q f , δ}
