自动机理论简介

自动机 – 它是什么？

"自动机"一词源于希腊语"αὐτόματα"，意为"自动行动"。自动机（复数为 Automata）是一种抽象的自推进计算设备，可自动遵循预定的操作序列。

具有有限状态数的自动机称为有限自动机 (FA) 或有限状态机 (FSM)。

有限自动机的正式定义

自动机可以用 5 元组 (Q、∑、δ、q₀、F) 表示，其中 −

• Q 是一组有限的状态。

• ∑ 是一组有限的符号，称为自动机的字母表。

• δ 是转换函数。

• q₀ 是处理任何输入的初始状态 (q₀ ∈ Q)。

• F 是 Q 的一组最终状态 (F ⊆ Q)。

相关术语

字母表

• 定义 − 字母表 是任何有限的符号集。

• 示例 − ∑ = {a, b, c, d} 是一个 字母表集，其中 'a'、'b'、'c' 和 'd' 是 符号。

字符串

• 定义 − 字符串 是从 ∑ 中获取的有限符号序列。

• 示例 − 'cabcad' 是字母表集 ∑ = {a, b, c, d} 上的有效字符串。

字符串的长度

• 定义 − 它是字符串中存在的符号数。 （用 |S| 表示）。

• 示例 −

  • 如果 S = 'cabcad'，|S|= 6

  • 如果 |S|= 0，则称为 空字符串（用 λ 或 ε 表示）

Kleene Star

• 定义 −克莱尼星号 ∑* 是符号或字符串集 ∑ 上的一元运算符，它给出 ∑ 上所有可能长度的所有可能字符串的无限集，包括 λ。

• 表示 − ∑* = ∑₀ ∪ ∑₁ ∪ ∑₂ ∪……。其中 ∑_p 是长度为 p 的所有可能字符串的集合。

• 示例 − 如果 ∑ = {a, b}, ∑* = {λ, a, b, aa, ab, ba, bb,………..>

Kleene 闭包 / Plus

• 定义 − 集合 ∑⁺ 是 ∑ 上所有可能长度（不包括 λ）的所有可能字符串的无限集。

• 表示 − ∑⁺ = ∑₁ ∪ ∑₂ ∪ ∑₃ ∪…….

  ∑⁺ = ∑* − { λ

• 示例 − 如果 ∑ = { a, b } ，则 ∑⁺ = { a, b, aa, ab, ba, bb,………..

语言

• 定义 − 对于某些字母表 ∑，语言是 ∑* 的子集。它可以是有限的，也可以是无限的。

• 示例 − 如果语言采用所有可能的字符串，长度为 2，超过 ∑ = {a，b}，则 L = {ab，aa，ba，bb }