自動機理論簡介

自動機 – 它是什麼？

"自動機"一詞源於希臘語 "αὐτόματα"，意為"自動"。自動機（複數為自動機）是一種抽象的自動計算裝置，它按照預定的操作序列自動執行。

具有有限狀態的自動機稱為有限自動機 (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 }