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.