IB 102 - úkol 10 - řešení
Odevzdání: 14.12. 2009
Vypracoval: James Bond                                UČO: 007
Skupina: MI6
1. [4 body] Je dána bezkontextová gramatika G = ({S, A, B, C}, {a, b, c}, P, S), kde
P = { S -»■ BC | aAb | cA, A ->■ BbB | baA | e, B ^cB\c, C^bCa\ aAb | bb }.
(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 uveďte akceptující výpočet nad slovem cbbabaa.
Řešení: (a) A = ({q}, {a, b, c}, {S, A,B, C,a, b, c}, ô, q, S, 0), kde ô je definována takto:
6(q,6,S) = {(q,BC),(q,aAb),(q,cA)}, 5(q,e,A) = {(q,BbB),(q,baA),(q,e)} 5(q,e,B) = {(q,cB),(q,c)}, 5{q,e,C) = {(q,bCa),(q,aAb),(q,bb)} 5(q, a, a) = 5(q, b, b) = 5(q, c, c) = {(q, e)}.
Akceptující výpočet nad slovem cbbabaa:
e                                                        see                                                      b
(q, cbbabaa, S) h (q, cbbabaa, B C) h (q, cbbabaa, cC) h (q,bbabaa,C) h (q,bbabaa,bCa) h
e                                         be                                         a                                    e
(q,babaa,Ca) h (q,babaa,bCaa) h (q,abaa,Caa) h (q,abaa,aAbaa) h (q,baa,Abaa) h
b                           a                     a
(q,baa,baa) h (q,aa,aa) h (q, a, a) h (q, e, e)
IB 102 - úkol 8 - řešení                                    Odevzdání: 30.11. 2009
Vypracoval: James Bond                                UCO: 007
Skupina: MI6
(b) A = ({q,r}, {a, b,c}, {S, A, B, C, a, b, c, _L}, ô, q, _L, {r}), kde ô je definována takto:
6(q,6,BC) = 6(q,6,cA) = {(q,S)},
S(q,e,BbB) = 6(q,e,baA) = ö(q,e,e) = {(q, A)},
5{q, e, cB) = 5(q, e, c) = {(q,B)},
ó(q,s,bCa) = ó(q,s,bb) = {(q,C)},
ó(q,s,aAb) = {(q,S),(q,C)},
6(q,a,e) = {{q,a)},
ó(q,b,s) = {(q,b)},
ö{q,c,e) = {(q,c)},
ó(q,s,±S) = {(r,s)}.
Akceptující výpočet nad slovem cbbabaa:
c                                         e                                           b                                           b
(q, cbbabaa, .L) h (q,bbabaa,A. c) h (q,bbabaa,A. B) h (q,babaa,A. Bb) h (q,abaa,A.
a                                          e                                              b                                              e                                         a
Bbb) h (q,baa,-L Bbba) h (q,baa,A. BbbaA) h (q,aa,A. BbbaAb) h (q,aa,A. BbbC) h (q,a,±BbbCa) h (q,a,±BbC) h (q,e,±BbCa) h (q,e,±BC) h (q, e, ±S) h (r, e, e)
IB 102 - úkol 10 - řešení
Odevzdání: 14.12. 2009
Vypracoval: James Bond Skupina: MI6
UCO: 007
2.  [2 body] Nechť L = {a%\Pck\Pa% \ i,j,k > 0, (i + j) mod 3 = k mod 3}. Zkonstruujte zásobníkový automat A akceptující prázdným zásobníkem jazyk L.
Řešení: Hledaný automat je A = ({qo,qi, 52, 93}, {«, b, c}, {Z, A, B, C}, ô, qo, Z, 0), kde
(qo,a,Z	) = {(
(Qo,b,Z)	= {(<
(Qo,£,Z)	= {(
(qo, a, A	) = {(
(qi, a, A	) = {(
(q2,a,A	) = {(
(qo,b,A)	= {(<
(qi,b,A)	= {(<
(Q2,b,A)	= {(<
(Qo,£,A)	= {(
(Qi,£,A)	= {(
(Q2,£,A)	= {(
(qo,b,B]	= {(
(qi,b,B)	= {(
(Q2,b,B)	= {(
(Qo,£,B	) = {(
(qi,e,B	) = {(
(Q2,£,B	) = {(
(Qo,c,C)	= {(
(Qi,c,C)	= {(
(Q2,C,C)	= {(
ÍQo,£,C]	= {(
(qsAB)	= {(
(q3,a,A	) = {(
(Q3,£,Z)	= {(
qi,AZ)} qi,BZ)} Qo,CZ)}
quAA)}
Q2,AA)} Qo,AA)} qi,BA)} Q2,BA)} Qo,BA)} qo,CA)} qi,CA)} Q2,CA)}
qi,BB)} Q2,BB)} Qo,BB)} qo,CB)} qi,CB)} q2,CB)}
q2,C)} qo,C)} qi,C)} qa,e)}
q3,e)} qa, e)}
Základní myšlenka konstrukce je, že v zásobníku uchováváme informaci, kolik znaků a, b je v první polovině slova a v druhé polovině slova kontrolujeme, zdali počet znaků a, b je stejný. Stavy qo,q\, (fe zajišťují splnění podmínky (i + j) mod 3 = k mod 3.