自动机理论简介

---

自动机——它是什么？

“自动机”一词源自希腊语“αὐτόματα”，意思是“自作用”。自动机（复数Automata）是一种抽象的自驱动计算设备，它自动遵循预定的操作顺序。

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

有限自动机的正式定义

_{自动机可以用 5 元组 (Q, Σ, δ, q 0} , 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 星Σ*是一组符号或字符串Σ上的一元运算符，它给出了 Σ 上所有可能长度的所有可能字符串的无限集合，包括λ。

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

• 示例- 如果 Σ = {a, b}, Σ* = {λ, a, b, aa, ab, ba, bb,………..}

Kleene 闭合 / Plus

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

• 表示− Σ ⁺ = Σ ₁ ∪ Σ ₂ ∪ Σ ₃ ∪……。

  Σ ⁺ = Σ* − { λ }

• 示例- 如果 Σ = { a, b } , Σ ⁺ = { a, b, aa, ab, ba, bb,………..}

语言

• 定义- 语言是某些字母表 Σ 的 Σ* 的子集。它可以是有限的或无限的。

• 示例- 如果语言在 Σ = {a, b} 上采用长度为 2 的所有可能字符串，则 L = { ab, aa, ba, bb }