NPDA與正好2的狀態，可能需要3點過渡到最終狀態

比方說，我們要畫一個NPDA的兩種狀態轉換圖是接受語言L.而且我們也說，這NPDA會恰好有2個州。我的想法是在第一個狀態下做所有事情，然後用第二個狀態作爲最後一個狀態。像這樣：

enter image description here

但我不知道該拉姆達的轉變將導致q1或是否有更好的方式來做到這一點，這有可能是一個更好的辦法，因爲我想教給我自己。也許有人可以讓我回到正軌？

2013-11-28 stackuser

這種CS理論對於計算器而言並不是真正的主題。在http://cs.stackexchange.com/上你會有更好的運氣。 –

似乎更適合CS –

你幾乎明白了。您剛剛錯過了n>=1的要求，因爲您目前的NPDA也會接受「acb」。而且你不需要（b，4）/ 5，因爲堆棧符號5不會被使用。

因此，您需要1和2之間的另一個堆棧符號來表示我們是否在「c」之前看到「b」。

 
q₀-q₀   q₀-q₁ 
(a,Z)/1Z  (b,3)/λ 
(b,1)/2  (b,4)/λ 
(b,2)/2  (b,5)/λ 
(c,2)/3 
(b,3)/4 
(b,4)/5

2013-11-28 05:46:51 justhalf

精彩的+1，我只是不確定我是完全理解你在最後一個'b'，因爲'm'可能是1,2或3，所以它看起來像就像這是3個可能的轉換'q0-q1'。我錯過了什麼？ – stackuser

對不起，你是對的，我遺漏了一個案例。編輯 – justhalf

回答