設計一個 NPDA 用於接受語言 L = {a^m b^(2m) | m>=1}

基本上，一個下推自動機 (PDA) 如下所示：

“有限狀態機 + 棧”

PDA 有三個組成部分，如下所示：

• 輸入帶。
• 控制單元。
• 一個無限大小的棧。

一個 PDA 可以正式地描述為七元組

(Q, Σ,S, δ,q0,I,F)

其中，

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

問題

構造一個非確定性 PDA (NPDA) 用於接受語言

L = {a^m b^2m | m>=1}。

解決方案

此語言生成的字串為：

L = {abb, aabbbb, aaabbbbbb, aaaabbbbbbbb, ......}

該語言計算 a 的數量，然後是兩倍數量的 b。

解釋

步驟 1 - 保持 a 和 b 的順序。

步驟 2 - 構建一個帶有狀態圖的棧。

步驟 3 - a 和 b 的數量由棧維護。

步驟 4 - b 的數量正好是 a 的數量的兩倍。

步驟 5 - 我們將使用 2 個棧字母

r = { a, z }

其中，

• r = 所有棧字母的集合
• z = 開始符號

給定問題的 PDA 構造

PDA 如下所示：

轉移函式

PDA 的轉移函式如下所示：

設計一個 NPDA，當 'a' 出現在 'b' 之前時將其壓入棧中，如果再次出現 'a' 則再次壓入。此外，當 'b' 出現時，從棧中彈出 'a'。

但我們對 b 的交替位置執行此彈出操作（對於兩個 b 彈出一個 'a'，對於四個 b 彈出兩個 'a'）。

最後，如果棧最終為空，則可以認為該字串被 PDA 接受。

Bhanu Priya

更新於：2021 年 6 月 15 日

601 次瀏覽

開啟你的 職業生涯

完成課程獲得認證

立即開始