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)