資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學構造用於anbn（其中n>=1）的確定性下推自動機 (DPDA)
問題
構造一個確定性下推自動機 (DPDA) 用於anbn，其中 n>=1。
解答
因此，由給定語言生成的字串如下：
L={ab, aabb, aaabbb,…}
也就是說，我們必須計算相同數量的a和b。
這可以透過將a壓入堆疊，然後在出現“b”時彈出a來實現。
最後，如果字串結尾時堆疊中沒有任何內容，則可以宣告該語言在PDA中被接受。
狀態轉換圖如下：
轉移函式
轉移函式如下：
δ(q0, a, Z) = (q0, aZ)
δ(q0, a, a) = (q0, aa)
δ(q0, b, a) = (q1, ε)
δ(q1, b, a) = (q1, ε)
δ(q1, ε, Z) = (qf, Z)
解釋
步驟1 - 讓我們取一個輸入字串：“aabb”。
步驟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 - 我們到達了字串的末尾，規則是：
輸入ε，堆疊字母為Z，進入最終狀態(qf)：(ε, Z/Z)
更新於：2021年6月15日
29K+ 次瀏覽
廣告