區分TOC中的DPDA和NPDA？

與有限自動機(FA)類似，下推自動機(PDA)可以是確定性的或非確定性的。

確定性下推自動機(DPDA)永遠沒有下一步的選擇 -

與確定性有限自動機(DFA)相比，它對每個狀態、輸入字元和堆疊字元的組合都有可能的輸出。

我們需要小心處理每個狀態和堆疊字元的組合。對於空符號∧或輸入符號，只允許一個事務。或者根本沒有事務。

示例

非確定性下推自動機(NPDA)可以包含以下指令，但DPDA不能包含這些指令。

• 例1 - (0, a, $,push(Y), 0); (0, a, $,pop, 1)

• 例2 - (0, ∧, $, pop, 3); (0, b, $, nop, 2)

示例

考慮偶數長度迴文 - L = {wwR | w ∈ {a, b}+}

狀態轉換圖如下：

這是一個NPDA的例子，因為從狀態0開始，它會分支，或者載入另一個字母，或者嘗試刪除字母。這隻能非確定性地完成。

DPDA需要知道何時開始從堆疊中刪除字母。因此，NPDA可以識別偶數迴文語言，但DPDA不能。

DPDA識別正則語言以及一些非正則語言，但並非所有上下文無關語言。

下圖描述了DPDA和NPDA在識別正則語言和上下文無關文法方面的區別：

Bhanu Priya

更新於：2021年6月15日

5K+ 次瀏覽

啟動你的職業生涯

透過完成課程獲得認證

開始