DPDA自動規則

Question

我無法理解VS DPDA NPDA之間的區別，我認爲它會像從多個選項，可採取到下一個狀態

的狀態這

NPDA- DPDA-從狀態，只有1路，可採取的下一個狀態

..但有2個關於DPDA，我不能得到

..per維基百科 黑白理解規則

的第一條規則：

• q是一個國家，一個是字母符號，x是堆棧符號

什麼是「至多有一個元素」的意思

我不知道第二條規則是什麼意思。

請問有人可以將此翻譯成純英文。我會很感激。

Answer 1

對於第一條規則，「至多有一個元素」意味着對於特定的輸入和堆棧符號只有一個delta轉換（delta轉換正式作爲PDA的集合對待）。換句話說，如果在堆棧頂部有輸入，輸入就沒有多個狀態了。

如您所述，「DPDA-從一個狀態開始，只有一條路徑可以進入下一個狀態。」這條規則是表示只能採取一條路徑的正式方式。

違反規則1可能會在相同的狀態下使用相同的輸入符號和堆棧符號指定兩個增量轉換。例如，從狀態q可能有兩個轉換，每個需要堆棧上的b和a作爲輸入，但轉到不同的狀態。這不會是DPDA。

第二條規則規定，如果堆棧符號下的空字符串存在delta轉換，那麼堆棧符號下的字母表中的任何字母都不會有delta轉換。

這意味着如果你允許一個特定的堆棧符號在沒有任何輸入的狀態下被彈出，你不能允許它也以相同的輸入狀態彈出。

違反規則2可能會允許從堆棧中彈出a s，但不會在2個狀態之間進行任何輸入，但也允許從b作爲輸入彈出堆棧中的a。