Automat ze stosem
Teoria automatów i języków
formalnych
Dr in\
. Janusz Majewski
Katedra Informatyki
Automat ze stosem (1)
Automat ze stosem (2)
A = < Ł, Q, F, q0 , �, Z0 , �, $ >
Ł  zbiór symboli terminalnych
Q  zbiór stanów #Q < "
F ą" Q  zbiór stanów końcowych
q0 " Q  stan początkowy
�  zbiór symboli stosowych
Z0 " � *" {�}  symbol początkowy stosu
� - funkcja przejścia
� : Q� (Ł *"{�,$})ד* a 2Qד*
$ - ogranicznik końca słowa wejściowego
Konfiguracja automatu
(opis chwilowy)
wierzchołek
stosu
stos taśma wejściowa
P R R R P R a b b a b a $
#
#
qi
Konfiguracja automatu: (#RRRPR, qi , baba$)
stos (wierzchołek stosu) stan nieprzeczytana część taśmy wejściowej
Akceptacja przez stan końcowy
Akceptacja przez pusty stos
Wyprowadzenie bezpośrednie
- pojedynczy krok automatu
Wyprowadzenie bezpośrednie
(",q, a�$) (" , q , �$)
A
", " " �*
q, q " Q
a " Ł *" {�}
*"
*"
*"
� " Ł*
to są początkowe symbole stosu, stos przyrasta  w prawo
(q , SUFFIX(" )) " �(q, b, SUFFIX("))
gdzie:
SUFFIX(ł)  przyrostek łańcucha ł
a
ńł - gdy a "Ł wtedy wejście jest czytane, głowica przesuwa się w prawo
�ł
b = � - gdy a = � wtedy wejście nie jest brane pod uwagę
�ł
�ł$ - gdy a = �, � = � oznacza całkowite przeczytanie wejścia
ół
Przykład: Automat ze stosem akceptujący
język L = { 0n1n | n = 0,1,...}
A= < Ł, Q, F, q0, �, Z0, �, $ >
Ł = { 0, 1}
Q = { q0, q1, q2}
F = {q0}
q0  stan początkowy
� = {R, 0 }
Z0 = R
(1) � (q0, 0, R} ={(q1, R0 )} Analizowane słowo: 000111$
(2) � (q1, 0, 0} ={(q1, 00 )} (R, q0, 000111$)
(1)
(3) � (q1, 1, 0} ={(q2, � )} (R0, q1, 00111$)
(2)
(4) � (q2, 1, 0} ={(q2, � )} (R00, q1, 0111$)
(2)
(5) � (q2, $, R} ={(q0, � )} (R000, q1, 111$)
(3)
(6) � (q0, $, R} ={(q0, � )} (R00, q2, 11$)
(4)
(R0, q2, 1$)
(4)
(R, q2, $)
(5)
( �, q0, $)
Akceptacja języka przez automat ze stosem
x"Ł* jest słowem akceptowanym przez automat A (ze stosem) przy
stanie końcowym �!
(" "F) ( (Z0, q0, x$) * (s, q, $); s"
"q" "�*)
" " "
" " "
A
Język L jest akceptowany przez automat A przy stanie końcowym (co
oznaczamy L(A)) �!
L = L(A) = {x"
"Ł* | x jest akceptowane przez A
"
"
przy stanie końcowym}
x"Ł* jest słowem akceptowanym przez automat A (ze stosem) przy
pustym stosie �!
(" "Q) ( (Z0, q0, x$) * (�, q, $) )
"q"
" "
" "
A
Język L jest akceptowany przez automat A przy pustym stosie (co
oznaczamy N(A)) �!
L = N(A) = {x"
"Ł* | x jest akceptowane przez A
"
"
przy pustym stosie}
Języki akceptowane przez automaty
ze stosem
Poni\
sze trzy klasy języków pokrywają się ze
sobą:
" Języki bezkontekstowe, czyli języki generowane
przez gramatyki bezkontekstowe
" Języki akceptowane przez automaty ze stosem
przy stanie końcowym
" Języki akceptowane przez automaty ze stosem
przy pustym stosie
Konstrukcja automatu ze stosem odtwarzającego
wywód lewostronny w gramatyce G"
"GBK
"
"
(top - down)
We: G = < V, Ł, P, S > " GBK
"
"
"
Wy: A = < Ł, Q, F, q0, �, Z0, �, $ >
taki, \
e N(A) = L(G)
Rozwiązanie:
Q : = {q};
F: = "
";
"
"
q0: = q;
� := V)"
)"Ł;
)"
)"
Z0: = S;
Przykład dla gramatyki wyra\
eń
Przykład:
G = <{E, T, F}, {id, +, *, ( , )},
P = { E E+T | T
T T*F | F
F (E) | id}, E >
A=<{id, +, *, ( , )}, {q}, " q, {E, T, F, id, +, *, ( , )}, E, �,
",
"
"
$>
�(q, �, E) ={(1)(q, T+E ), (2)(q, T)}
�(q, �, T) ={(3)(q, F*T ), (4)(q, F)}
�(q, �, F) ={(5)(q, )E( ), (6)(q, id )}
�(q, b, b) ={(pop)(q, �)} dla wszystkich b"
"{ id, +, *, ( , )}
"
"
Analiza słowa:  id + id * id
E, q, id + id * id $ (1)
E
T+E, q, id + id * id $ (2)
E + T
T+T, q, id + id * id $ (4)
T + T
T+F, q, id + id * id $ (6)
F + T
T+ id , q, id + id * id $ (pop)
id + T
T+ , q, + id * id $ (pop)
id + T
T , q, id * id $ (3)
id + T
F * T, q, id * id $ (4)
id + T * F
F * F , q, id * id $ (6)
id + F * F
F * id, q, id * id $ (pop)
id + id * F
(pop)
F * , q, * id $
id + id * F
(6)
F , q, id $
id + id * F
(pop)
id, q, id $
id + id * id
�, q, $
id + id * id
Akceptacja przez pusty stos
Symbole zdjęte przez (pop)
Konstrukcja automatu ze stosem odtwarzającego
wywód prawostronny (bottom-up)
w gramatyce G"
"GBK
"
"
We: G = < V, Ł, P, S > "GBK
"
"
"
Wy: A = < Ł, Q, F, q0, �, Z0, �, $ >
taki, \
e L(A) = L(G)
Rozwiązanie:
Q := {q0, q1};
F := {q1};
� := V *" Ł *" {#}; /* # - dodatkowy symbol */
Z0 := #;
for a " Ł do
"
"
"
Wyprowadzenie lewostronne
top-down
Przykład gramatyki wyra\
eń
G = <{E, T, F}, {id, +, *, ( , )},
{ E E+T | T
T T* F | F
F (E) | id }, E >
A = <{ id, +, *, ( , )}, {q0, q1}, {q1}, q0, {E, T, F, id, +, *, ( , ), #}, #, $>
�(q0, b, �} = {(q0, b)} dla wszystkich b"
"{ id, +, *, ( , )}
"
"
(shift)
�(q0, �, E + T} = {(q0, E)}
(1)
�(q0, �, T } = {(q0, E)}
(2)
�(q0, �, T*F } = {(q0, T)}
(3)
�(q0, �, F} = {(q0, T)}
(4)
�(q0, �, (E)} = {(q0, F)}
(5)
�(q0, �, id } = {(q0, F)}
(6)
�(q0, $, #E } = {(q1, �)}
(acc)
Analiza słowa:  id + id * id
#, q0, id + id * id $ (shift)
id + id * id
(6)
# id, q0, + id * id $
(4)
# F, q0, + id * id $
F + id * id
(2)
#T, q0, + id * id $
T + id * id
(shift)
#E, q0, + id * id $
E + id * id
(shift)
#E +, q0, id * id $
(6)
#E + id, q0, * id $
(4)
#E + F, q0, * id $
E + F * id
(shift)
#E + T, q0, * id $
E + T * id
(shift
#E + T*, q0, id $
)
(6)
#E + T* id, q0, $
(3)
#E + T *F, q0, $
E + T * F
(1)
#E + T , q0, $
E + T
(acc)
#E , q0, $
E
�, q1, $
Wyprowadzenie prawostronne bottom-up.
Wierzchołek stosu przy redukcjach
to prawa granica osnowy
Deterministyczny automat ze stosem
A = < Ł, Q, F, q0, �, Z0, �, $ > - automat ze stosem jest
deterministyczny �!
(i) ( "q"Q ) ( "a"Ł *" {�, $} ) ( "ł"�* ) ( #�(q, a, ł) d" 1 )
(ii) ( �(q, a, ą) `" " '" �(q, a, �) `" " '" ą `" � ) �! \
aden z
łańcuchów: ą oraz � nie jest przyrostkiem drugiego łańcucha
(iii) ( �(q, a, ą) `" " '" �(q, �, �) `" " ) �! \
aden z łańcuchów:
ą oraz � nie jest przyrostkiem drugiego łańcucha
Twierdzenie: Klasa języków akceptowanych przez
deterministyczne automaty ze stosem jest właściwą
podklasą klasy języków akceptowanych przez automaty ze
stosem.
Innymi słowy: nie dla ka\
dego automatu ze stosem istnieje
równowa\
ny mu deterministyczny automat ze stosem.
L(ADeterministyczny ze Stosem) �" L(Aze Stosem)
Przykład
L={xxR | x"Ł*}  jest językiem nieakceptowalnym przez
deterministyczny automat ze stosem.
Przypuśćmy, \
e A jest automatem ze stosem akceptującym język L
i niech y"Ł* będzie dowolnym słowem przeznaczonym do analizy
przez automat. Aby sprawdzić, czy y jest postaci xxR trzeba
przepisać lewą połowę słowa y na stos, tzn. przejść od
konfiguracji (�, q0, xxR$) do konfiguracji (x, q, xR$), a następnie
przystąpić do sprawdzenia, czy słowo na stosie jest
zwierciadlanym odbiciem słowa pozostającego na wejściu. Takie
postępowanie wymaga umiejętności odszukiwania połowy
(środka) słowa y, co przy jednokrotnym jego czytaniu jest
oczywiście niemo\
liwe.
Mo\
na pokazać, \
e deterministyczny automat akceptujący język L
istnieje, nie jest to ju\
jednak automat ze stosem, ale automat
liniowo ograniczony.