資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究構建用於 a(n+m)bmcn (n,m≥1) 的 DPDA（在 TOC 中）
下推自動機 (PDA) 可以正式地描述為七元組
(Q, Σ,S, δ,q0,I,F)
其中，
- Q 是有限數量的狀態
- Σ 是輸入字母表
- S 是棧符號
- Δ 是轉移函式：QX(Σ∪{e})XSXQ
- q0 是初始狀態（q0 屬於 Q）
- I 是初始棧頂符號
- F 是接受狀態集
問題
構建用於 a(n+m)bmcn (n,m≥1) 的 PDA。
解決方案
因此，由給定語言生成的字串為 -
L={aabc,aaaabccc,aaaaabbccc,….}
也就是說，將 b 和 c 的數量相加，這將等於 a 的數量。
對於每個 b 和 c，我們將從棧中彈出 a。
讓我們計算 a 的數量，它等於 b 和 c 的數量之和。
可以透過將 a 推入棧中來實現，然後在出現“b”或“c”時彈出 a。
最後，在字串的末尾，如果棧中沒有剩餘任何內容，那麼我們可以說 PDA 接受了該語言。
給定問題的 PDA 如下 -
轉移函式
轉移函式如下 -
步驟 1：δ(q0, a, Z) = (q0, aZ)
步驟 2：δ(q0, a, a) = (q0, aa)
步驟 3：δ(q0, b, a) = (q1, ε)
步驟 4：δ(q1, b, a) = (q1, ε)
步驟 5：δ(q1, c, a) = (q2, ε)
步驟 6：δ(q2, c, a) = (q2, ε)
步驟 7：δ(q2, ε, Z) = (qf, Z)
解釋
步驟 1 - 讓我們取一個輸入字串：“aaaabbcc”，它滿足給定條件。
步驟 2 - 從左到右掃描字串。
步驟 3 - 對於輸入 'a' 和棧字母 Z，則
將輸入 'a' 推入棧中：(a,Z/aZ)，狀態將為 q0
步驟 4 - 對於輸入 'a' 和棧字母 'a'，則
將輸入 'a' 推入棧中：(a,a/aa)，狀態將為 q0
步驟 5 - 對於輸入 'a' 和棧字母 'a'，則
將輸入 'a' 推入棧中：(a,a/aa)，狀態將為 q0
步驟 6 - 對於輸入 'a' 和棧字母 'a'，則
將輸入 'a' 推入棧中：(a,a/aa)，狀態將為 q0
步驟 7 - 對於輸入 'b' 和棧字母 'a'，狀態為 q0，則
彈出 'a'：(c,a/ε)，狀態將為 q1
步驟 8 - 對於輸入 'b' 和棧字母 'a'，狀態為 q1，則
彈出 'a'：(c,a/ε)，狀態保持為 q1
步驟 9 - 對於輸入 'c' 和棧字母 'a'，狀態為 q1，則
彈出 'a'：(c,a/ε)，狀態將為 q2
步驟 10 - 對於輸入 'c' 和棧字母 'a'，狀態為 q2，則
彈出 'a'：(c,a/ε)，狀態保持為 q2
步驟 11 - 我們到達了字串的末尾，輸入為 ε，棧字母為 Z，則
轉到最終狀態(qf)：(ε, Z/Z)
879 次瀏覽
