IB102 ­ úkol 11 ­ řešení Odevzdání: 15. 12. 2008
Vypracoval: James Bond UČO: 007
Skupina: MI6
1. [2 body] Je dána bezkontextová gramatika G = ({S, A, B, C, D}, {a, k, l, o}, P, S), kde
P = { S  AB | DB,
A  k | AB
B  o | BD | SC,
C  a | AC | SA,
D  l | DC | AC}
Pomocí Cocke-Younger-Kasami algoritmu rozhodněte, zda kolaloka  L(G).
Řešení:
1 2 3 4 5 6 7 8
8 {S, A, B, C, D}
7 {S, A, B, C, D} {B}
6 {S, A} {B} {S, D}
5 {S, A, B} ­ {D} ­
4 {S, A, B, C, D} {B} ­ ­ {S, B}
3 {S, A} {B} ­ ­ {C} {B}
2 {S, A} {B} {D} ­ {S} ­ {C, D}
1 {A} {B} {D} {C} {D} {B} {A} {C}
k o l a l o k a
Platí, že S  T1,8, tudíž kolaloka  L(G).
IB102 ­ úkol 11 ­ řešení Odevzdání: 15. 12. 2008
Vypracoval: James Bond UČO: 007
Skupina: MI6
2. [4 body] Je dána bezkontextová gramatika G = ({S, A, B}, {a, b, c}, P, S), kde
P = { S  SS | ABS | cA | cB,
A  bA | bAa | ,
B  bbB | ba | bc | a }.
(a) Sestrojte odpovídající PDA, který provádí nedeterministickou syntaktickou analýzu
shora dolů.
(b) Sestrojte odpovídající rozšířený PDA, který provádí nedeterministickou syntaktickou
analýzu zdola nahoru.
Pro každý automat uvedťe akceptující výpočet nad slovem bbbcca.
Řešení:
(a) Sestrojíme PDA akceptující prázdnym zásobníkem, který provádí nedeterministickou
syntaktickou analýzu shora dolů (návod - věta 3.47 a její důkaz):
A = ({q}, {a, b, c}, {S, A, B, a, b, c}, , q, S, ), kde
(q, , S) = {(q, SS), (q, ABS), (q, cA), (q, cB)},
(q, , A) = {(q, bA), (q, bAa), (q, )}
(q, , B) = {(q, bbB), (q, ba), (q, bc), (q, a)},
(q, a, a) = {(q, )},
(q, b, b) = {(q, )},
(q, c, c) = {(q, )}.
Akceptující výpočet nad slovem bbbcca:
(q, bbbcca, S)

(q, bbbcca, ABS)

(q, bbbcca, bABS)
b
(q, bbcca, ABS)

(q, bbcca, bABS)
b
(q, bcca, ABS)

(q, bcca, BS)

(q, bca, bcS)
b
(q, cca, cS)
c
(q, ca, S)

(q, ca, cB)
c
(q, a, B)

(q, a, a)
a
(q, , )
­ pokračování na další straně ­
IB102 ­ úkol 11 ­ řešení Odevzdání: 15. 12. 2008
Vypracoval: James Bond UČO: 007
Skupina: MI6
(b) Sestrojíme rozšířený PDA akceptující koncovým stavem, který provádí nedeterministickou
syntaktickou analýzu zdola nahoru (návod - věta 3.55 a její důkaz):
A = ({q, r}, {a, b, c}, {S, A, B, a, b, c, }, , q, , {r}), kde
(q, , SS) = (q, , ABS) = (q, , cA) = (q, , cB) = {(q, S)},
(q, , bA) = (q, , bAa) = (q, , ) = {(q, A)},
(q, , bbB) = (q, , ba) = (q, , bc) = (q, , a) = {(q, B)},
(q, a, ) = {(q, a)},
(q, b, ) = {(q, b)},
(q, c, ) = {(q, c)},
(q, , S) = {(r, )}.
Akceptující výpočet nad slovem bbbcca:
(q, bbbcca, )
b
(q, bbcca,  b)
b
(q, bcca,  bb)

(q, bcca,  bbA)

(q, bcca,  bA)

(q, bcca,  A)
b
(q, cca,  Ab)
c
(q, ca,  Abc)

(q, ca,  AB)
c
(q, a,  ABc)
a
(q, , ABca)

(q, , ABcB)

(q, , ABS)

(q, , S)

(r, , ).