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