構造一個用於anb2n (n ≥ 1) 的確定性下推自動機 (DPDA)

確定性有限自動機 (DFA) 只能記住有限的資訊，而下推自動機 (PDA) 則可以記住無限的資訊。

基本上，PDA 如下所示：

“有限狀態機 + 堆疊”

PDA 有三個組成部分：

• 輸入帶
• 控制單元
• 大小無限的堆疊

PDA 可以正式描述為七元組 (Q, Σ, S, δ, q0, I, F)

• Q 是有限數量的狀態
• Σ 是輸入字母表
• S 是堆疊符號
• Δ 是轉移函式：QX(Σ∪{e})XSXQ
• q0 是初始狀態 (q0屬於Q)
• I 是初始狀態頂部符號
• F 是一組接受狀態

問題

構造一個用於 aⁿb²ⁿ (n ≥ 1) 的 PDA。

解決方案

因此，由給定語言生成的字串如下：

L={abb,aabbbb,aaabbbbbb,…}

這裡 a 後面跟著兩倍數量的 b。

每當出現 'a' 時，就在堆疊中壓入兩個 'a'，如果再次出現 'a'，則執行相同的操作。

當出現 'b' 時，每次從堆疊中彈出 'a'。請注意，'b' 出現在 'a' 之後。

最後，在字串結束時，如果堆疊中沒有任何內容，那麼我們可以宣告該語言在 PDA 中被接受。

問題的PDA 如下所示：

轉移函式

轉移函式如下所示：

步驟 1：δ(q0, a, Z) = (q0, aaZ)

步驟 2：δ(q0, a, a) = (q0, aaa)

步驟 3：δ(q0, b, a) = (q1, ε)

步驟 4：δ(q1, b, a) = (q1, ε)

步驟 5：δ(q1, ε, Z) = (qf, Z)

解釋

步驟 1 - 考慮輸入字串：“aabbbb”，它滿足給定條件。

步驟 2 - 從左到右掃描字串。

步驟 3 - 對於輸入 'a' 和堆疊字母 Z，則

步驟 4 - 對於輸入 'a' 和堆疊字母 'a'，則

將兩個 'a' 壓入堆疊：(a,a/aaa)，狀態將為 q0。現在堆疊有“aaaa”。

步驟 5 - 對於輸入 'b' 和堆疊字母 'a'，則

從堆疊中彈出 'a'：(b,a/ε)，狀態將為 q1。

步驟 6 - 對於輸入 'b'，堆疊字母 'a' 和狀態 q1，則

從堆疊中彈出 'a'：(b,a/ε)，狀態將保持 q1

步驟 7 - 對於輸入 'b' 和堆疊字母 'a'，則

從堆疊中彈出 'a'：(b,a/ε)，狀態將為 q1

步驟 8 - 對於輸入 'b'，堆疊字母 'a' 和狀態 q1，則

從堆疊中彈出 'a'：(b,a/ε)，狀態將保持 q1

步驟 9 - 我們到達字串末尾，對於輸入 ε 和堆疊字母 Z，

轉到最終狀態 (qf)：(ε, Z/Z)

Bhanu Priya

更新於：2021年6月15日

2萬+ 次瀏覽

啟動您的職業生涯

透過完成課程獲得認證

開始學習