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