什麼是瞬時描述和轉向臺符號?


下推自動機 (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' 沒有被接受。

更新於:2021年6月16日

1K+ 次檢視

啟動您的 職業生涯

完成課程獲得認證

開始
廣告