什麼是佇列自動機？

佇列自動機類似於下推自動機 (PDA)，只是堆疊被佇列替換。

• 佇列是一條磁帶，只能在左側寫入符號，只能在右側讀取符號。

• 每個寫操作（我們稱之為推入）都會在佇列的左側新增一個符號，每個讀操作（我們稱之為拉出）都會讀取並刪除右側的符號。

• 與 PDA 一樣，輸入放在單獨的只讀輸入帶上，輸入帶上的磁頭只能從左到右移動。

• 輸入帶包含一個帶有空白符號的單元格，該單元格位於輸入之後，以便可以檢測輸入的結尾。

• 佇列自動機透過在任何時間進入一個特殊的接受狀態來接受其輸入。

形式化定義

確定性佇列自動機 (DQA) 定義為七元組

(Q, Σ, Γ, δ, q0 , ⊥, F)

其中，

• Q 是一組狀態，

• Σ 是輸入字母表，

• Γ 是一個有限的佇列符號集，

• q0 是起始狀態，

• ⊥ 是一個空佇列符號 ⊥6= Γ，

• 轉移函式 δ 定義為 Q × Σ ∪ {λ} × (Γ × Γ) ∪ ({⊥} × {⊥}) → Q × Γ ∪ {λ} × {keep, remove}，其中 λ 表示空符號。它絕不能用作輸入符號。

• F 是一組接受狀態 (F ⊆ Q)。

示例

為語言 {aⁿbⁿ | n >= 0} 構造佇列自動機。

對於給定的語言，自動機中存在的狀態數為 4，

Q={q0,q1,q2,q3}，

輸入字母表 ={a,b}

佇列自動機如下所示 -

Bhanu Priya

更新於: 2021年6月15日

470 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習