設計：一^^IB 2I

Question

我學爲我的考試自動機和形式語言，我要設計識別語言中的PDA：

一個^ IB^2I使得i> = 1

我認爲該解決方案將是：

每個 「A」 從磁帶上讀出I堆棧兩個X然後，如果我得到一個 「b」 上磁帶和我在堆棧頂部有一個X，我彈出一個X堆棧，最後，如果我讀空磁帶，並且我有Zo（堆棧標記的底部），字符串被接受。我的問題是：我可以在一個計算步驟中堆疊兩個連續的X？

Answer 1

你不需要在一個步驟中推兩個X，只需按下一個X，然後轉換到另一個X而不從磁帶中消耗任何東西的狀態。請記住，轉換函數是sigion UNION {ε}，因此您可以在不消耗任何輸入的情況下處理堆棧。

簡答：你想做N件事情到堆棧？設N個狀態。只要確定N是事先知道的:)

Answer 2

我可以在一個計算步驟中堆疊兩個連續的X？

這取決於你如何定義「下推自動機」，特別是你如何定義轉換函數。您當然可以定義PDA以便一次推送整個字符串。你需要檢查你的課程文本或與你的教授，看看是否會允許這種事情在課程中。