下推自動機（PDA）

Question

我試圖寫一個PDA下推自動機接受^ 2n個b^N，N-> 0 但我不知道，如果最後一部分是正確的

(p0, a, z0) = (p0, az0) 
(p0, a, a) = (p0, aa) 
(p0, b, a) = (p1, λ) 
(p1, λ, b) = (p2, λ) <= 
(p2, 0, b) = (p1, λ) <= 
(p2, λ, z0) = (p3, λ) <= 

Answer 1

就你的答案而言，在你的前兩步中，你只需要一步就能完成。使用目前的設計，機器會接受aaabb，而不是a^2nb^n的形式。所以最好將它分爲兩​​個狀態。據我正確的答案可能是這樣的：

1. （P0，一，Z0）=（P0，az0）
2. （P0，A，A）=（P1，AA）
3. （ P1，A，A）=（P0，AA）
4. （P1，b，A）=（P2，λ）

Answer 2

確定性下推自動機用於^ 2NB ^ン> = 0
旁路奧特萊納特a和推動其餘的一個的