3.5. Automat ze stosem
A = < T, Q, F, q
0
, S, s
0
,
δ
>
T – zbiór symboli terminalnych
Q – zbiór stanów #Q <
∞
F
⊆
Q – zbiór stanów końcowych
q
0
∈
Q – stan początkowy
S – zbiór symboli stosowych
s
0
∈
S
∪
{
ε
}
δ
- funkcja przejścia
*
*
2
,$})
{
(
:
S
Q
S
T
Q
×
×
∪
×
!
ε
δ
$ - ogranicznik końca słowa wejściowego
wierzchołek stosu
stos
taśma wejściowa
Konfiguracja automatu
(P R R P R, q
i
, b a b a $)
stos
stan Nieprzeczytana
część taśmy
wejściowej
Wierzchołek stosu
Konfiguracja początkowa: (s
0
, q
0
, w$): w
∈
T
*
R
P
R
P
a
b
a
R
b
b
a
$
q
i
s
0
W
$
q
0
Konfiguracja końcowa: (
ε
, q, $): q
∈
F
Stos pusty
Wyprowadzenie bezpośrednie
(
∂
,q, a
τ
$)
"
A
(
∂
’
, q
’
,
τ
$)
∂
,
∂
’
∈
S
*
q, q
’
∈
S
a
∈
T
∪
{
ε
}
τ
∈
T
*
to są początkowe symbole stosu, stos przyrasta “w prawo”
(q
’
, SUFFIX(
∂
’
))
∈
δ
(q, b, SUFFIX(
∂
))
gdzie:
SUFFIX(
γ
) – przyrostek łańcucha
γ
→
wtedy wejście jest czytane, głowica przesuwa się w prawo
→
wtedy wejście nie jest brane pod uwagę
→
oznacza to całkowite przeczytanie wejścia
Wyprowadzenia pośrednie "
A
+
oraz "
A
*
są odpowiednio przechodnim oraz przechodnim i
zwrotnym domknięciem relacji wyprowadzenia bezpośredniego "
A
.
Przykład: Automat ze stosem akceptujący język L = { 0
n
1
n
| n = 0,1...}
A= < T, Q, F, q
0
, S, s
0
, δ, $ >
T = { 0, 1}
Q = { q
0
, q
1
, q
2
}; F = {q
0
}
q
0
– stan początkowy
S = {R, 0 }
s
0
= R
(1) δ (q
0
, 0, R} ={(q
1
, R0 )}
(2) δ (q
1
, 0, 0} ={(q
1
, 00 )}
(3) δ (q
1
, 1, 0} ={(q
2
, ε )}
(4) δ (q
2
, 1, 0} ={(q
2
, ε )}
(5) δ (q
2
, $, R} ={(q
0
, ε )}
(6) δ (q
0
, $, R} ={(q
0
, ε )}
w
$
q
∈
F
=
=
=
∈
=
ε
τ
ε
ε
ε
,
a
gdy
-
$
a
gdy
-
a
gdy
-
a
T
b
G = < N, T, P, Z >
∈
G
BK
N = {Z}
T = { 0 , 1}
P = {Z
→
0Z1 | ε }
Analizowane słowo:
(R, q
0
, 000111$ )
"
(1)
(R0, q
1
, 00111$)
"
(2)
(R00, q
1
, 0111$)
"
(2)
(R000, q
1
, 111$)
"
(3)
(R00, q
2
, 11$)
"
(4)
(R0, q
2
, 1$)
"
(4)
(R, q
2
, $)
"
(5)
( ε, q
0
, $)
x
∈
T* jest słowem akceptowanym przez automat A (ze stosem)
⇔
(
∃
q
∈
F ) ( (s
0
, q
0
, x$) "
A
*
( ε, q, $) )
Język L jest akceptowany przez automat A (co oznaczamy L(A))
⇔
L = L(A) = {x
∈
T* | x jest akceptowane przez A}
Tw. Dla każdej gramatyki bezkontekstowej G
∈
G
BK
istnieje automat ze stosem A, taki, że
L(A) = L(G)
Def. Odbiciem zwierciadlanym (rewersem) słowa x
∈
V* gdzie x = x
1
x
2
... x
n
, x
i
∈
V jest
słowo x
R
= x
n
x
n-1
...x
2
x
1
Konstrukcja automatu ze stosem odtwarzającego wywód lewostronny w gramatyce G
∈
G
BK
(top - down)
We: G = < N, T, P, Z >
∈
G
BK
Wy: A = < T, Q, F, q
0
, S, s
0
, δ, $ >
taki, że L(A) = L(G)
Rozwiązanie
Q : = {q};
F: = {q};
q
0
: = q;
S := N
∩
T;
s
0
: = Z;
for (A
→
x)
∈
P do
do δ (q, ε, A) włącz (q, x
R
);
for a
∈
T do
do δ (q, a, a) włącz (q, ε);
000111$
Przykład:
G = <{E, T, F}, {id, +, *, ( , )},
P = { E
→
E+T | T
T
→
T* F | F
F
→
(E) | id},
E >
A = <{ id, +, *, ( , )}, {q}, {q}, q, {E, T, F, id, +, *, ( , )}, E, δ, $>
δ (q, ε , E} ={
(1)
(q, T+ F ),
(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, +, *, ( , )}
Analizowane słowo:
E, q, id + id * id $
"
(1)
T+ E, q, id + id * id $
"
(2)
T+T, q, id + id * id $
"
(4)
T+F, q, id + id * id $
"
(6)
T+ id , q, id + id * id $
"
(pop)
T + , q, + id * id $
"
(pop)
T , q, id * id $
"
(3)
F * T, q, id * id $
"
(4)
F * F , q, id * id $
"
(6)
F * id, q, id * id $
"
(pop)
F * , q, * id $
"
(pop)
F , q, id $
"
(6)
id, q, id $
"
(pop)
ε, q, $ :
E
E + T
T + T
F + T
id + T
id + T
id + T
id + T * F
id + F * F
id + id * F
id + id * F
id + id * F
id + id * id
id + id * id
To jest automat
NIEDETERMINISTYCZNY
Konstrukcja automatu ze stosem odtwarzającego wywód prawostronny (bottom-up) w
gramatyce G
∈
G
BK
We: G = < N, T, P, Z >
∈
G
BK
Wy: A = < T, Q, F, q
0
, S, s
0
, δ, $ >
taki, że L(G) = L(A)
Rozwiązanie
Q : = {q
0
, q
1
};
F: = { q
1
};
S := N
∪
T
∪
{#}; /* # - dod. symbol */
s
0
: = #;
for a
∈
T (A
→
x)
∈
P do
do δ (q
0
, a, ε) włącz (q
0
, a);
for (A
→
x)
∈
P do
do δ (q
0
, ε, x) włącz (q
0
, A);
do δ (q
0
, $, #Z) włącz (q
1
, ε);
id + id * id
Sy
mbole z
dj
ęte
p
rze
z
(pop)
W
yprowadz
enie
lewostronne top-
down
Przykład:
G = <{E, T, F}, {id, +, *, ( , )},
{ E
→
E+T | T
T
→
T* F | F
F
→
(E) | id },
E >
A = <{ id, +, *, ( , )}, {q
0
, q
1
}, {q
1
}, q
0
, {E, T, F, id, +, *, ( , ), #}, #, $>
(Shift)
δ (q
0
, b, ε} ={( q
0
, b)} dla wszystkich b
∈
{ id, +, *, ( , )}
(1)
δ (q
0
, ε, E + T} ={(q
0
, E )}
(2)
δ (q
0
, ε, T } ={(q
0
, E )}
(3)
δ (q
0
, ε, T*F } ={(q
0
, T )}
(4)
δ (q
0
, ε, F} ={(q
0
, T )}
(5)
δ (q
0
, ε, (E)} ={(q
0
, F )}
(6)
δ (q
0
, ε, id } ={(q
0
, F)}
(acc)
δ (q
0
, $, #E } ={(q
1
, ε)}
Analizowane słowo:
#, q
0
, id + id * id $
# id, q
0
, + id * id $
# F, q
0
, + id * id $
#T, q
0
, + id * id $
#E, q
0
, + id * id $
#E +, q
0
, id * id $
#E + id, q
0
, * id $
#E + F, q
0
, * id $
#E + T, q
0
, * id $
#E + T*, q
0
, id $
#E + T* id, q
0
, $
#E + T *F, q
0
, $
#E + T , q
0
, $
#E , q
0
, $
ε, q
1
, $
:
"
(Shift)
"
(6)
"
(4)
"
(2)
"
(Shift)
"
(Shift)
"
(6)
"
(4)
"
(Shift)
"
(Shift)
"
(6)
"
(3)
"
(1)
"
(acc)
id + id * id
F + id * id
T + id * id
E + id * id
E + F * id
E + T * id
E + T * F
E + T
E
Deterministyczny automat ze stosem
A = < T, Q, F, q
0,
S, s
0
,
δ
, $ > - automat ze stosem jest deterministyczny
⇔
(i) (
∀
q
∈
Q ) (
∀
a
∈
T
∪
{
ε
, $} ) (
∀γ∈
S
*
) ( #
δ
(q, a,
γ
)
≤
1 )
(ii) (
δ
(q, a,
α
)
≠
φ
∧
δ
(q, a,
β
)
≠
φ
∧
α
≠
β
)
⇒
żaden z łańcuchów:
α
oraz
β
nie jest przyrostkiem drugiego łańcucha
(iii) (
δ
(q, a,
α
)
≠
φ
∧
δ
(q, a,
β
)
≠
φ
)
⇒
żaden z łańcuchów:
α
oraz
β
nie jest
przyrostkiem drugiego łańcucha
Tw. 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 (A
Deterministyczny ze Stosem
)
⊂
L (A
ze Stosem
)
id + id * id
Wy
prow
adzen
ie
praw
os
tr
on
ne
bot
to
m
-u
p.
Wie
rzc
ho
łek stosu prz
y redukcjach
to
prawa g
rani
ca osnowy
Przykład:
L={xx
R
: x
∈
T
*
} – 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
∈
T
*
będzie dowolnym słowem przeznaczonym do analizy przez automat.
Aby sprawdzić, czy y jest postaci xx
R
trzeba przepisać lewą połowę słowa y na stos, tzn.
przejść od konfiguracji (
ε
, q
0
, xx
R
$) do konfiguracji (x, q, x
R
$), 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 jednokrotnie 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.
Gramatyka generująca L, przykład:
G=< {Z}, {a,b}, P, Z >
Z
→
aZa | bZb |
ε
WARUNEK KONIECZNY BEZKONTEKSTOWOŚCI JĘZYKA
Tw. Jeżeli L
∈
α
BK
To
∃
k: (w
∈
L
∧
|w|
≥
k)
⇒
(w = xuyvz
∧
uv
≠ε
∧
|uyv|
≤
k
∧
∀
i
≥
0 : xu
i
yv
i
z
∈
L )
Jest to tzw. Lemat o rozrastaniu się języków bezkontekstowych. Mówi on o tym, że każde
dostatecznie długie słowo języka bezkontekstowego da się przedstawić w postaci xuyvz oraz
Wszystkie słowa o postaci xu
i
yv
i
z (i
≥
0) też będą należały do tego samego języka.
xyz = xu
0
yv
0
z
w
x y z
|w|
≥
k
x u y v z
......
x u
i
y v
i
z
Przykład:
L
1
= { a
i
b
i
c
i
; i
≥
0 } nie jest językiem bezkontekstowym
L
2
= { a
i
b
i
; i
≥
0 } jest językiem bezkontekstowym (bo istnieje akceptujący go automat ze
stosem
→
był przykład)