什麼是瞬時描述和轉向臺符號?
下推自動機 (PDA) 的瞬時描述 (ID) 由三元組 (q, w, s) 表示。
其中:
- q 是狀態。
- w 是未使用的輸入。
- s 是堆疊內容。
ID 是 PDA 如何比較輸入字串並做出接受或拒絕該字串的決定的非正式表示。
轉向臺符號
它用於連線表示 PDA 一次或多次移動的 ID 對。
轉換過程用轉向臺符號“⊢”表示。
⊢ 表示一次移動。
⊢ 符號描述一系列移動。
示例
(P, b, T) ⊢ (q, w, a)
在從 P 到 q 進行轉換時,消耗輸入符號 'b',並表示堆疊頂部 'T'。
考慮另一個示例,以瞭解更多關於 ID 和轉向臺符號的資訊
問題:找出 PDA 輸入字串 w = "aaabb" 的 ID,並檢查字串是否被 PDA 接受?
解決方案:讓我們看看字串 w = "aaabb" 的瞬時描述
(q0, aaabb, Z0) |- (q0, aabb, aZ0) {基於轉換規則 1}
|- (q0, abb, aaZ0) {基於轉換規則 2}
|- (q0, bb, aaaZ0) {基於轉換規則 2}
|- (q1, b, aaZ0) {基於轉換規則 3}
|- (q1, λ, aZ0) {基於轉換規則 3}
|- 沒有定義移動。
因此,下推自動機最終在此移動處停止,並且字串不被接受,因為輸入字串 w 已完成或輸入帶為空,但 PDA 堆疊不為空。
所以字串 'w' 沒有被接受。
廣告