資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究當一個字串被NPDA接受或拒絕時會發生什麼？
如果存在從起始狀態到最終狀態的某個路徑（即指令序列），並且該路徑消耗了字串的所有字母，則非確定性下推自動機 (NPDA) 接受該字串。否則，NPDA 拒絕該字串。
NPDA 的語言是它接受的所有字串的集合。
在以下情況下，輸入字串會被NPDA拒絕：
如果讀取輸入字串完成但沒有到達最終狀態。
如果對於當前狀態/棧上的符號/輸入符號不存在轉換。
如果嘗試彈出空棧。
示例
構建一個識別上下文無關語言的NPDA
L = {anbn| n > 0}。
步驟
按照以下步驟構建NPDA：
開始讀取字串，對於每個讀取到的a，將一個Y壓入棧中。
在第一個b出現時更改狀態，並開始為每個b從棧中彈出一個Y。
如果到達輸入的末尾並且剛剛清空了棧，則接受字串。
否則，拒絕。例如，如果在輸入結束前棧就為空了——b的數量多於a的數量。
用於 { anbn , n>=0} 的下推自動機
三個狀態 - 0（開始）、1、2（最終）
輸入字母表 - {a,b}
棧字母表 - { Y,$}
下推自動機如下所示：
此NPDA有六條允許的指令，如下所示：
T1 - (0, a, $, push(Y), 0)
T2 - (0, a, Y, push(Y), 0)
T3 - (0, ∧, $, nop, 2)
T4 - (0, b, Y, pop, 1)
T5 - (1, b, Y, pop, 1)
T6 - (1, ∧, $, nop, 2)
讀取$對應於檢查棧是否為空。
更新於：2021年6月15日
252次瀏覽
廣告