資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究構造用於 anbncm 的DPDA，其中n、m≥1（在TOC中）
DPDA是確定性下推自動機（DPDA）的簡稱。
問題
構造用於 anbncm 的DPDA，其中 m、n>=1
解決方案
因此，由給定語言生成的字串為：
L={abc,aabbc,aaabbbcc,…}
也就是說，我們必須計算相同數量的a、b和不同數量的c。
讓我們計算a的數量，它等於b的數量。
這可以透過將a壓入棧中來實現，然後在遇到“b”時彈出a。
然後對於c，什麼也不會發生。
最後，在字串的末尾，如果棧中沒有任何東西剩下，那麼我們可以說該語言在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, Z) = (qf, Z)
步驟6 - δ(qf, c, Z) = (qf, Z)
解釋
步驟1 - 考慮一個輸入字串：“aabbcc”，它滿足給定條件。
步驟2 - 從左到右掃描字串。
步驟3 - 第一個輸入是'a'，規則為
對於輸入'a'和棧字母Z，則
將輸入'a'壓入棧：(a,Z/aZ)，狀態將為q0
步驟4 - 第二個輸入是'a'，規則為
對於輸入'a'和棧字母'a'，則
將輸入'a'壓入棧：(a,a/aa)，狀態將為q0
步驟5 - 第三個輸入是'b'，規則為
對於輸入'b'和棧字母'a'，則
彈出棧中的一個'a'：(b,a/ε)，狀態現在將為q1
步驟6 - 第四個輸入是'b'，規則為：
對於輸入'b'，棧字母'a'，狀態為q1，則
彈出棧中的一個'a'：(b,a/ε)，狀態將為q1
步驟7 - 第五個輸入是'c'，棧頂為Z，規則為
對於輸入'c'，棧字母'Z'，狀態為q1，則
不做任何操作：(c,Z/Z)，狀態將為qf
步驟8 - 第六個輸入是'c'，棧頂為Z，規則為
對於輸入'c'，棧字母'Z'，狀態為qf，則
不做任何操作：(c,Z/Z)，狀態將為qf
步驟9 - 我們到達了字串的末尾，規則為
如果我們處於最終狀態qf，則字串在PDA中被接受
1K+ 瀏覽量
