資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究構造一個下推自動機 (PDA)，它接受 (a,b)* 語言，但不包含子串 bbbb。
下推自動機 (PDA) 是包含子串 bbb 的 PDA 的補集。
步驟
建立一個 PDA 來接受包含子串 bbb 的字串。
透過將非接受狀態設為接受狀態，反之亦然，來取其補集。
構造 PDA
您可以像下面所示那樣為(a,b)* 語言構造 PDA
轉換格式的性質是：輸入、棧頂、PUSH/POP
示例
a , a , aa 表示當輸入為 a 且棧頂為 a 時，壓入 a
在 q0（初始狀態），如果輸入是 a 或 b，則狀態轉移到 q1。
直到 q1 我們得到一個 b 來構成子串 b_ _，現在如果在 q1 輸入 a，則會破壞 bbb 的模式。所以像上面 PDA 中所示那樣轉移到 q0。
但是如果得到 b, b, bb，這意味著輸入是 b 且棧頂是 b。壓入 bb，現在模式是 bb_，並轉移到狀態 q2。
現在在 q2，我們得到 2 個 bb 來構成子串 bb_。現在，如果在 q2 輸入 a，則會破壞 bbb 的模式。所以像上面 PDA 中所示那樣轉移到 q0。
但是如果得到 b, b, bb，這意味著輸入是 b 且棧頂是 b。壓入 bb，現在模式是 bbb，並轉移到狀態 q4。
在狀態 q4，我們已經完成了子串 bbb。所以現在，接受 a 或 b 任何符號。
當整個字串結束且狀態為 q4 時，我們轉移到狀態 q5。
現在，如果我們想要接受包含 bbb 作為子串的字串的語言，那麼 q5 是最終狀態。
- 但是我們的問題是我們不想要 bbb。所以所有其他狀態都是最終狀態，即 q0、q1、q2、q4 都是最終狀態。
所以，PDA 構造完成。
更新於：2021年6月16日
516 次瀏覽
廣告