Akceptacja automatów pushdown
Istnieją dwa różne sposoby definiowania akceptowalności urządzeń PDA.
Dopuszczalność stanu końcowego
W stanie końcowym akceptowalnym, PDA akceptuje ciąg znaków, gdy po odczytaniu całego ciągu PDA jest w stanie końcowym. Od stanu początkowego możemy wykonywać ruchy, które kończą się stanem końcowym z dowolnymi wartościami stosu. Wartości stosu są nieistotne, dopóki osiągniemy stan ostateczny.
Dla PDA (Q, ∑, S, δ, q 0 , I, F) językiem akceptowanym przez zbiór stanów końcowych F jest -
L (PDA) = {w | (q 0 , w, I) ⊢ * (q, ε, x), q ∈ F}
dla dowolnego ciągu stosu wejściowego x.
Dopuszczalność pustego stosu
Tutaj PDA akceptuje ciąg znaków, gdy po odczytaniu całego ciągu PDA opróżnił swój stos.
W przypadku PDA (Q, ∑, S, δ, q 0 , I, F) językiem akceptowanym przez pusty stos jest -
L (PDA) = {w | (q 0 , w, I) ⊢ * (q, ε, ε), q ∈ Q}
Przykład
Skonstruuj PDA, który akceptuje L = {0n 1n | n ≥ 0}
Rozwiązanie
Ten język akceptuje L = {ε, 01, 0011, 000111, .............................}
Tutaj, w tym przykładzie, liczba ‘a’ i ‘b’ muszą być takie same.
Początkowo umieściliśmy specjalny symbol ‘$’ do pustego stosu.
Następnie w stanie q2, jeśli napotkamy wejście 0 i top ma wartość Null, wsuwamy 0 do stosu. To może się powtarzać. A jeśli napotkamy dane wejściowe 1, a top wynosi 0, to zerujemy.
Następnie w stanie q3, jeśli napotkamy dane wejściowe 1, a top jest równy 0, usuniemy to 0. Może to również spowodować iterację. A jeśli napotkamy dane wejściowe 1 i top jest 0, usuwamy górny element.
Jeśli na szczycie stosu zostanie napotkany specjalny symbol „$”, jest on wyskakiwany i ostatecznie przechodzi do stanu akceptacji q 4 .
Przykład
Skonstruuj PDA akceptujący L = {ww R | w = (a + b) *}
Solution
Początkowo umieszczamy specjalny symbol „$” w pustym stosie. W stanieq2, the wczyta się. Uroczyścieq3, każde 0 lub 1 jest usuwane, gdy pasuje do wejścia. Jeśli podane zostanie jakiekolwiek inne wejście, PDA przejdzie w stan nieaktywny. Kiedy osiągamy ten specjalny symbol „$”, przechodzimy do stanu akceptacjiq4.