Automat ze stosem (PDA)
Automat z dodatkową pamięcią w postaci stosu (widać tylko ostatnio
włożony symbol).
Przykład: Palindrom z gramatyką S 0S0|1S1|#
Automat ze stosem
1
Automat startuje z pustym stosem i w stanie q1.
Języki formalne i techniki translacji - Wykład 5
2
Jeżeli jesteśmy w stanie q1 i na wejściu widzimy a " {0, 1} to
wstawiamy a na stos, pozostajemy w stanie q1 i idziemy do
następnego symbolu wejściowego.
Maciek Gębala
3
Jeżeli jesteśmy w stanie q1 i na wejściu widzimy # to
przechodzimy do stanu q2 i idziemy do następnego symbolu
wejściowego.
20 marca 2013
4
Jeżeli jesteśmy w stanie q2 i na wejściu widzimy a " {0, 1} i na
stosie jest także a to pozostajemy w stanie q2, ściągamy a ze
stosu i idziemy do następnego symbolu wejściowego.
5
Jeżeli jesteśmy w stanie q2, skończyliśmy czytać wejście i stos
jest pusty to akceptujemy słowo wejściowe.
6
W każdym innym przypadku odrzucamy słowo wejściowe.
Maciek Gębala Automat ze stosem Maciek Gębala Automat ze stosem
Automat ze stosem (PDA) Automat ze stosem (PDA)
Definicja. Relacja przejścia w jednym kroku :
M
Definicja. Automatem ze stosem nazywamy
(q, aą, Z ł) (pi, ą, łił) jeśli istnieje przejście
M = (Q, Ł, �, �, q0, Z0, F ), gdzie
M
�(q, a, Z ) = {(p1, ł1), . . . , (pm, łm)} i wybraliśmy i-tą możliwość.
Q - skończony zbiór stanów,
(q, ą, Z ł) (pi, ą, łił) jeśli istnieje przejście
Ł - alfabet wejściowy,
M
�(q, �, Z ) = {(p1, ł1), . . . , (pm, łm)} i wybraliśmy i-tą możliwość.
� - alfabet stosowy,
" - zwrotne i przechodnie domknięcie . i - i-krotne złożenie .
q0 " Q - stan początkowy,
Z0 " � - symbol początkowy na stosie,
Język akceptowany przez PDA M przy pustym stosie (F = ") to
F �" Q - zbiór stanów akceptujących (jeśli F = " to
akceptujemy przez pusty stos),
N(M) = { w " Ł" : "p"Q (q0, w, Z0) " (p, �, �) }
"
� - funkcja przejścia postaci � : Q � (Ł *" {�}) � � 2Qד
Język akceptowany przez PDA M przez stan końcowy to
Definicja. Opis chwilowy automatu to trójka (q, ą, ł), gdzie q " Q -
"
L(M) = { w " Ł" : "p"F "ł"� (q0, w, Z0) " (p, �, ł) }
stan automatu, ą " Ł" - nieprzeczytane jeszcze wejście, ł " �" -
zawartość stosu (szczyt stosu z lewej).
Oba sposoby akceptowania są równoważne.
Maciek Gębala Automat ze stosem Maciek Gębala Automat ze stosem
Przykład Deterministyczny DFA
M = ({q1, q2}, {0, 1}, {A, B, Z }, �, q1, Z , ")
� (0, A) (0, B) (0, Z ) (1, A) (1, B) (1, Z ) (�, A) (�, B) (�, Z )
q1 (q1, AA) (q1, AB) (q1, A) (q1, BA) (q1, BB) (q1, B) (q2, A) (q2, B) (q2, �)
q2 (q2, �) - - - (q2, �) - - - -
PDA nazwiemy deterministycznym jeśli w każdym przypadku
możemy wykonać co najwyżej jedno przejście, czyli jeśli
0110
1
"q"Q "Z "� �(q, �, Z ) = " =�! "a"Ł �(q, a, Z ) = "

(q1, 0110, Z ) (q1, 110, A) (q1, 10, BA) (q2, 10, BA) (q2, 0, A) (q2, �, �)
2
"q"Q "a"Ł*"{�} "Z "� |�(q, a, Z )| 1
110
Niestety DPDA są słabsze od PDA np. język z poprzedniego slajdu
nie jest rozpoznawalny przez żaden DPDA.
(q1, 110, Z ) (q1, 10, B) (q1, 0, BB) (q1, �, ABB) (q2, �, ABB) ?
(q1, 110, Z ) (q1, 10, B) (q1, 0, BB) (q2, 0, BB) ?
(q1, 110, Z ) (q1, 10, B) (q2, 10, B) (q2, 0, �) ?
(q1, 110, Z ) (q2, 100, �) ?
N(M) = { wwR : w " {0, 1}" }
Maciek Gębala Automat ze stosem Maciek Gębala Automat ze stosem
PDA i gramatyka bezkontekstowa Przykład
Twierdzenie. Jeśli L jest językiem bezkontekstowym to istnieje PDA
M taki, że L = N(M).
G = ({A, B}, {a, b}, {A aAB|aB, B b}, A)
Dowód
Załóżmy, że L nie zawiera � i jest zdefiniowany przez gramatykę
M = ({q}, {a, b}, {A, B}, �, q, A, ")
bezkontekstową w postaci Greibach G = (N, T , P, S). Definiujemy
� (a, A) (a, B) (b, A) (b, B) (�, A) (�, B)
PDA M następująco
q (q, AB), (q, B) - - (q, �) - -
M = ({q}, T , N, �, q, S, ") �(q, a, A) = { (q, ł) : (A ał) " P }.
M symuluje wyprowadzenie lewostronne gramatyki G. Ponieważ G
A �! aAB �! aaBB �! aabB �! aabb
jest typu Greibach każdy kolejny napis w wyprowadzeniu
"
lewostronnym ma formę xą gdzie x " T i ą " N". M przechowuje ą
na stosie po przeczytaniu przedrostka x.
Teraz dowód indukcyjny po długości wyprowadzenia (ilości kroków), (q, aabb, A) (q, abb, AB) (q, bb, BB) (q, b, B) (q, �, �)
że
S �!" x �!�! (q, x, S) " (q, �, �)
G M
Maciek Gębala Automat ze stosem Maciek Gębala Automat ze stosem
PDA i gramatyka bezkontekstowa PDA i gramatyka bezkontekstowa
Twierdzenie. Jeśli L = N(M) dla PDA M to L jest językiem
bezkontekstowym.
Dowód
Dowód cd.
Wez
my PDA M = (Q, Ł, �, �, q0, Z0, "). Konstruujemy gramatykę
[q, A, p] wyprowadza x �!�! M będąc w stanie q i mając na stosie
bezkontekstową G = (N, Ł, P, S), gdzie
Aą po wczytaniu x znajdzie się w stanie q, na stosie będzie ą i ą nie
N - zbiór obiektów postaci [q, A, p] (p, q " Q, A " �), oraz nowy
była zmieniana i czytana w tym czasie.
symbol S,
Teraz dowód indukcyjny po ilości kroków, że
P - zbiór produkcji postaci:
[q, A, p] �!" x �!�! (q, x, A) " (p, �, �)
S [q0, Z0, q] dla każdego q " Q, G M
[q, A, qm+1] a[q1, B1, q2][q2, B2, q3] . . . [qm, Bm, qm+1] dla
dowolnych q, q1, . . . , qm+1 " Q, każdego a " Ł *" {�} i dowolnych
A, B1, . . . , Bm " � takich że (q1, B1 . . . Bm) " �(q, a, A), oraz
[q, A, p] a jeśli (p, �) " �(q, a, A).
Wyprowadzenie lewostronne w G symuluje ruchy M na wejściu x.
Maciek Gębala Automat ze stosem Maciek Gębala Automat ze stosem
Przykład Przykład cd.
M = ({p, q}, {a, b}, {X , Z }, �, p, Z , ")
Po usunięciu symboli bezużytecznych
� (a, X ) (a, Z ) (b, X ) (b, Z ) (�, X) (�, Z )
G = ({S, [p, Z , q], [p, X , q], [q, X , q]}, {a, b}, P, S)
p (p, XX) (p, X ) (q, �) - - (q, �)
q - - (q, �) - - -
S [p, Z , q]
[p, Z , q] a[p, X , q] | �
[p, X , q] a[p, X , q][q, X , q] | b
G = ({S, [p, Z , p], [p, Z , q], [q, Z , p], [q, Z , q], [p, X , p], [p, X , q], [q, X , p], [q, X, q]}, {a, b}, P, S)
[q, X , q] b
S [p, Z , p] | [p, Z , q]
[p, Z , p] a[p, X , p]
[p, Z , q] a[p, X , q] | �
(p, aabb, Z ) (p, abb, X ) (p, bb, XX ) (q, b, X) (q, �, �)
[q, Z , p]
[q, Z , q]
[p, X , p] a[p, X , p][p, X, p] | a[p, X , q][q, X , p]
[p, X , q] a[p, X , p][p, X, q] | a[p, X , q][q, X , q] | b
[p, Z , q] �! a[p, X , q] �! aa[p, X , q][q, X , q] �! aab[q, X, q] �! aabb
[q, X , p]
[q, X , q] b
Maciek Gębala Automat ze stosem Maciek Gębala Automat ze stosem