資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學用C++構造用於L = {0n1m2m3n | m,n ≥ 0}的下推自動機
我們得到了一種語言“L”，任務是為這種語言構造一個下推自動機。該語言規定0的出現次數與3的出現次數相等，1的出現次數與2的出現次數相等，並且所有數字的出現次數都至少為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 接受的字串形式為：
0n3n - 03, 0033, 000333 等。0 的數量等於 3 的數量。當 m 為 0 時，將沒有 1 和 2。不斷壓入 0，一旦遇到第一個 3，就彈出 0。如果到達字串末尾並且沒有剩餘的 0，則接受該字串。
1m2m - 12, 1122, 111222 等。1 的數量等於 2 的數量。當 n 為 0 時，將沒有 0 和 3。不斷壓入 1，一旦遇到第一個 2，就彈出 1。如果到達字串末尾並且沒有剩餘的 1，則接受該字串。
0n1m2m3n - 0123, 001233, 011223 等。0 的數量等於 3 的數量，1 的數量等於 2 的數量。不斷壓入 0 和 1。一旦遇到第一個 2，如果棧頂是 1 就彈出 1，然後對於其餘的 3 彈出 0。如果到達字串末尾並且沒有剩餘的 0，則接受該字串。
空字串也被接受：00102030。
讓我們理解這個機器
狀態 q0 的轉移：
( 0, I/0I ) − 如果棧頂是 I 且當前輸入符號是 0，則將 0 壓入棧頂並停留在 q0。棧變為 0I…
( 0, 0/00 ) − 如果棧頂是 0 且當前輸入符號也是 0，則將 0 壓入棧頂並停留在 q0。棧變為 00… 不斷壓入 0 直到下一個 1 或 3。
( 1, 0/10 ) − 如果棧頂是 0 且當前輸入符號是 1，則將 1 壓入棧頂並移動到 q1。棧變為 10…
( 1, I/1I ) − 如果棧頂是 I 且當前輸入符號是 1，則壓入 1 並移動到 q5。
( 3, 0/ε ) − 如果棧頂是 0 且當前輸入符號是 3，則彈出 0 並移動到 q3。
( $, I/I ) − 如果棧頂是 I 且沒有輸入，則不做任何操作並移動到 q4。（空字串的情況）
狀態 q1 的轉移：
( 1, 1/11 ) − 如果棧頂是 1 且當前輸入符號也是 1，則將 1 壓入棧頂並停留在 q1。棧變為 11… 不斷壓入 1 直到下一個 2。
( 2, 1/ε ) − 如果棧頂是 1 且當前輸入符號是 2，則彈出 1 並移動到 q2。
狀態 q2 的轉移：
( 2, 1/ε ) − 如果棧頂是 1 且當前輸入符號是 2，則彈出 1 並停留在 q2。
( 3, 0/ε ) − 如果棧頂是 0 且當前輸入符號是 3，則彈出 0 並移動到 q3。
狀態 q3 的轉移：
( 3, 0/ε ) − 如果棧頂是 0 且當前輸入符號是 3，則彈出 0 並停留在 q3。
( $, I/I ) − 如果棧頂是 I 且沒有輸入，則不做任何操作並移動到 q4。（空字串的情況）
狀態 q5 的轉移：
( 1, 1/11 ) − 如果棧頂是 1 且當前輸入符號也是 1，則將 1 壓入棧頂並停留在 q5。棧變為 11… 不斷壓入 1 直到下一個 2。
( 2, 1/ε ) − 如果棧頂是 1 且當前輸入符號是 2，則彈出 1 並移動到 q6。
狀態 q6 的轉移：
( 2, 1/ε ) − 如果棧頂是 1 且當前輸入符號是 2，則彈出 1 並停留在 q6。
( $, I/I ) − 如果棧頂是 I 且沒有輸入，則不做任何操作並移動到 q4。（空字串的情況）
605 次瀏覽
