資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用C++構建用於語言L = {0(n+m)1m2n | m, n = 0}的下推自動機。
給定一種語言“L”，任務是為該語言構建一個下推自動機。該語言說明0的出現次數將等於1和2的出現次數之和，並且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可以接受的字串形式為：
1. 0n2n：02、0022、000222等。0的個數等於2的個數。當m為0時，沒有1。不斷壓入0，一旦遇到第一個2，則彈出0。如果到達字串末尾並且沒有剩餘0，則接受該字串。
0m1m：01、0011、000111等。0的個數等於1的個數。當n為0時，沒有2。不斷壓入0，一旦遇到第一個1，則彈出0。如果到達字串末尾並且沒有剩餘0，則接受該字串。
0n+m1m2n：0012、000112、000122等。0的個數等於1和2的個數之和。不斷壓入0，一旦遇到第一個1，則彈出0直到沒有1。然後再次壓入0，一旦遇到第一個2，則彈出0直到沒有2。該字串將被接受。
空字串也被接受。001020
讓我們瞭解一下這個機器
狀態q0的轉移
(0, I/0I) - 如果棧頂為I且當前輸入符號為0，則將0壓入棧頂並保持在q0。棧變為0I…
(0, 0/00) - 如果棧頂為0且當前輸入符號也為0，則將0壓入棧頂並保持在q0。棧變為00… 不斷壓入0直到下一個1或2。
(1, 0/$) - 如果棧頂為0且當前輸入符號為1，則彈出0並移動到q1。
(2, 0/$) - 如果棧頂為0且當前輸入符號為2，則彈出0並移動到q2。
($, I/I) - 如果棧頂為I且沒有輸入，則不做任何操作並移動到qf。對於空字串。
狀態q1的轉移：
(1, 0/$) - 如果棧頂為0且當前輸入符號為1，則彈出0並保持在q1。
($, I/I) - 如果棧頂為I且沒有輸入，則不做任何操作並移動到qf。
(2, 0/$) - 如果棧頂為0且當前輸入符號為2，則彈出0並移動到q2。
狀態q2的轉移：
(2, 0/$) - 如果棧頂為0且當前輸入符號為2，則彈出0並保持在q2。
($, I/I) - 如果棧頂為I且沒有輸入，則不做任何操作並移動到qf。
388 次瀏覽
