資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究用C++構建用於L = {a(2*m)c(4*n)dnbm | m,n = 0}的下推自動機
給定一種語言“L”，任務是為該語言構建一個下推自動機。該語言規定字元'a'的出現次數應為字元'b'出現次數的兩倍，字元'c'的出現次數應為字元'd'出現次數的四倍，所有字元的出現次數至少為1，也允許空字串，並且空字串應被自動機接受。
什麼是下推自動機？
下推自動機 (PDA) 是一種實現上下文無關文法的技術，類似於我們為正則文法設計確定性有限自動機 (DFA) 的方式。DFA 可以操作有限資料，而 PDA 可以操作無限資料。我們可以將下推自動機理解為“有限狀態機”和“棧”的組合。
下推自動機有三個組成部分：
輸入帶；
控制單元；以及
大小無限的棧。
PDA 可以正式地描述為一個 7 元組 (Q, Σ, S, δ, q0, I, F)：
Q 是有限數量的狀態
Σ 是輸入字母表
S 是棧符號
δ 是轉移函式：Q × (Σ υ {ε}) × S × Q × S*
q0 是初始狀態 (q0 Ε Q)
I 是初始棧頂符號 (I Ε S)
F 是一組接受狀態 (F Ε Q)
讓我們為給定的語言構建一個下推自動機：
這個 PDA 接受的字串形式為：
c4ndn − ccccd，cccccccccdd 等。c 的數量是 d 的數量的 4 倍。當 m 為 0 時，將沒有 a 和 b。不斷壓入 c，一旦遇到第一個 d，就從棧中彈出 4 個 c。如果到達字串末尾並且沒有剩餘的 c，則接受該字串。
a2mbm − aab，aaaabb 等。a 的數量是 b 的數量的兩倍。當 n 為 0 時，將沒有 c 和 d。不斷壓入 a，一旦遇到第一個 b，就從棧中彈出 2 個 a。如果到達字串末尾並且沒有剩餘的 a，則接受該字串。
a2mc4ndnbm − aaccccdb，aaaaccccccccddbb 等。a 的數量是 b 的數量的兩倍，c 的數量是 d 的數量的四倍。不斷壓入 a 和 c。一旦遇到第一個 d，就彈出 4 個 c（如果在棧頂），然後為剩餘的 b 彈出 2 個 a。如果到達字串末尾並且沒有剩餘的 a，則接受該字串。
空字串也被接受：a0c0d0b0。
讓我們理解這個機器
狀態 q0 的轉移：
( a, I/a,I ) − 如果棧頂是 I 且當前輸入符號是 a，則將 a 壓入棧頂並保持在 q0。棧變為 aI…
( c, I/c,I ) − 如果棧頂是 I 且當前輸入符號是 c，則將 c 壓入棧頂並保持在 q0。棧變為 cI…
( a, a/a,a ) − 如果棧頂是 a 且當前輸入符號也是 a，則將 a 壓入棧頂並保持在 q0。棧變為 aa… 繼續壓入 a 直到下一個 c 或 b。
( c, c/c,c ) − 如果棧頂是 c 且當前輸入符號也是 c，則將 c 壓入棧頂並保持在 q0。棧變為 cc… 繼續壓入 c 直到下一個 d。
( b, a/e,aa ) − 如果棧頂是 a 且當前輸入符號是 b，則從棧中彈出 2 個 a 並移動到 q3。
(c, a/c,a ) − 如果棧頂是 a 且當前輸入符號是 c，則將 c 壓入棧頂並移動到 q1。棧變為 ca…
( d, c/e,cccc ) − 如果棧頂是 c 且當前輸入符號是 d，則從棧中彈出 4 個 c 並移動到 q4。
( $, I/I, I) − 如果棧頂是 I 且沒有輸入，則什麼也不做並移動到 q5。用於空字串。
狀態 q1 的轉移：
( c, c/c,c ) − 如果棧頂是 c 且當前輸入符號也是 c，則將 c 壓入棧頂並保持在 q1。棧變為 cc… 繼續壓入 c 直到下一個 d。
( d, c/e,cccc ) − 如果棧頂是 c 且當前輸入符號是 d，則從棧中彈出 4 個 c 並移動到 q2。
狀態 q2 的轉移：
( d, c/e,cccc ) − 如果棧頂是 c 且當前輸入符號是 d，則從棧中彈出 4 個 c 並移動到 q2。
( b, a/e,aa ) − 如果棧頂是 a 且當前輸入符號是 b，則從棧中彈出 2 個 a 並移動到 q3。
狀態 q3 的轉移：
( b, a/e,aa ) − 如果棧頂是 a 且當前輸入符號是 b，則從棧中彈出 2 個 a 並保持在 q3。
( $, I/I, I ) − 如果棧頂是 I 且沒有輸入，則什麼也不做並移動到 q5。用於空字串。
狀態 q4 的轉移：
( d, c/e,cccc ) − 如果棧頂是 c 且當前輸入符號是 d，則從棧中彈出 4 個 c 並保持在 q4。
( $, I/I, I ) − 如果棧頂是 I 且沒有輸入，則什麼也不做並移動到 q5。用於空字串。
496 次瀏覽
