自动机理论简介

自动机 – 它是什么？

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

具有有限状态的自动机称为有限自动机 (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，则称为空字符串（用λ或ε表示）

克莱尼星号

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

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

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

克莱尼闭包 / 加号

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

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

  ∑⁺ = ∑* − { λ }

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

语言

• 定义 - 语言是对于某个字母表 ∑ 的 ∑* 的子集。它可以是有限的或无限的。

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