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