解釋圖靈機變體雙棧下推自動機？

雙棧下推自動機 (PDA) 包括以下因素：

  • 圖靈機可以接受任何單棧 PDA 都無法接受的語言。

  • 透過新增額外的棧來增強下推自動機的功能。

  • 具有兩個棧的 PDA 與圖靈機具有相同的計算能力。

雙棧 PDA 是一種計算模型，它基於下推自動機 (PDA) 和非確定性雙棧 PDA 的泛化，而確定性雙棧 PDA 等價於非確定性雙棧 PDA。

雙棧 PDA 的移動基於以下內容：

  • 有限控制的狀態。

  • 讀取的輸入符號。

  • 每個棧的棧頂符號。

圖靈機 (TM) 和雙棧下推自動機 (雙棧 PDA) 機的一些特性如下：

圖靈機雙棧 PDA 機
更改狀態。更改狀態。
在掃描的單元格中寫入磁帶符號。讀取的輸入符號。
將磁頭向左或向右移動。用零個或多個棧符號的字串替換每個棧的符號。

下圖是 TM 變體雙棧 PDA 機。

磁帶的右半部分儲存在一個棧上，左半部分儲存在另一個棧上。

隨著我們移動，我們從一個棧彈出字元並將它們壓入另一個棧。

更新於：2021年6月16日

14K+ 瀏覽量

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告