自动机理论简介

Question

自动机是什么？

术语 自动机 源自希腊语 αὐτόματα ，意为 自作用 。自动机（复数形式的自动机) 是一种自动执行预定操作顺序的抽象自走式计算设备。

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

有限自动机的形式定义

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

• Q是一组有限的状态。
• ∑是一组有限的符号，称为自动机的字母。
• δ是转移函数。
• Q ₀是从那里的任何输入被处理(Q _0∈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 闭合/加号

• 定义 - 集合 ∑ ⁺是∑上除λ以外的所有可能长度的所有可能字符串的无限集合。
• 表示形式 - ∑ ⁺ = ∑ ₁ ∑ ₂ ∑ ∑ ₃ ………。
• ∑ ⁺ = ∑ * − {λ}
• 示例 - 如果 ∑ = {a，b}，∑ ⁺ = {a，b，aa，ab，ba，bb，……..}

语言

• 定义-语言是某个字母 ∑ 的 ∑ * 的子集。它可以是有限的或无限的。
• 示例-如果语言采用 ∑ = {a，b} 上所有可能的长度为 2 的字符串，则 L = {ab，aa，ba，bb}