設計一個下推自動機用於識別語言 L = {ww^R | w ∈ {a, b}+}？

下推自動機用於實現上下文無關文法，就像我們使用某種技術為正則文法設計確定性有限自動機一樣。DFA 使用有限的資訊量工作，而 PDA 使用無限的資訊量工作。

通常，下推自動機是：

"有限狀態機" + "一個棧"

下推自動機包含三個組成部分：

• 一個輸入帶；

• 一個控制單元；以及

• 一個無限大小的棧。

現在考慮一個問題：如何為給定的語言設計下推自動機？

問題

設計一個識別偶數長度迴文串的下推自動機，用於語言 **L = {ww^R | w ∈ {a, b}+}**。

解答

• 讀取字串並將其儲存到棧中。

• 在每一步中，考慮您可能已到達中間點的可能性。

• 一旦到達中點，就開始反向工作，如果匹配已儲存的內容，則從棧中移除內容。

在每一步，我們都需要測試我們是否位於字串的中間。

以下是字串 **aabbaa** 的逐步瞬時描述：

• 開始 → (0, aabbaa, $)

• 載入棧 → (0, abbaa, X$)

• 載入棧 → (0, bbaa, XX$)

• 載入棧 → (0, baa, YXX$)

• 嘗試，這是中間點嗎？ → (1, baa, YXX$)

• 彈出棧 → (1, aa, XX$)

• 彈出棧 → (1, a, X$)

• 彈出棧 → (1, ∧, $)

• 完成！ → (2, ∧, $)

Bhanu Priya

更新於：2021年6月15日

7K+ 瀏覽量

開啟你的職業生涯

完成課程獲得認證

開始學習