IB102 ­ úkol 10 ­ řešení Odevzdání: 8. 12. 2008
Vypracoval: James Bond UČO: 007
Skupina: MI6
1. [2 body] Mějme bezkontextovou gramatiku G = ({S, A, B, C, D}, {a, b, c}, P, S), kde
P = { S  AB | ABD,
A  BbA | C,
B  Ac,
C  abC | ,
D  aD }.
Zkonstruujte ekvivalentní gramatiku v Greibachové normální formě. Popište svůj postup,
uvedťe hlavní mezivýsledky.
Řešení: Gramatika G není vlastní, je proto nutné provést další úpravy před samotným
převodem do GNF. Použijeme algoritmy prezentované na přednášce.
Začneme odstraněním nepoužitelných symbolů, čím dostaneme gramatiku
G1 = ({S, A, B, C}, {a, b, c}, P1, S), kde
P1 = { S  AB,
A  BbA | C,
B  Ac,
C  abC |  }.
Následně odstraníme -pravidla. Pravidlá výsledné gramatiky
G2 = ({S, A, B, C}, {a, b, c}, P2, S) vypadají takhle:
P2 = { S  AB | B,
A  BbA | C | Bb,
B  Ac | c,
C  abC | ab }.
Pokračujeme eliminací jednoduchých pravidel, čím získáme gramatiku
G3 = ({S, A, B, C}, {a, b, c}, P3, S), kde:
P3 = { S  AB | Ac | c,
A  BbA | Bb | abC | ab,
B  Ac | c,
C  abC | ab }.
V této chvíli máme vlastní gramatiku, můžeme tedy přistoupit k odstranění levé rekurze.
Vytvoříme gramatiku G4 = ({S, A, B, C, B }, {a, b, c}, P4, S), kde
P4 = { S  AB | Ac | c,
A  BbA | Bb | abC | ab,
B  c | abCc | abc | cB | abCcB | abcB ,
B  bAc | bc | bAcB | bcB ,
C  abC | ab }.
Nakonec vzniklou gramatiku transformujeme do GNF. Výsledkem je ekvivalentní gramatika
G5 = ({S, A, B, C, B , b , c }, {a, b, c}, P5, S), kde
P5 = { S  c | ab CB | ab B | cb AB | ab Cc b AB | ab c b AB | cB b AB | ab Cc B b AB,
S  ab c B b AB | cb B | ab Cc b B | ab c b B | cB b B | ab Cc B b B | ab c B b B,
S  ab Cc | ab c | cb Ac | ab Cc b Ac | ab c b Ac | cB b Ac | ab Cc B b Ac ,
S  ab c B b Ac | cb c | ab Cc b c | ab c b c | cB b c | ab Cc B b c | ab c B b c ,
A  ab C | ab | cb A | ab Cc b A | ab c b A | cB b A | ab Cc B b A | ab c B b A | cb ,
A  ab Cc b | ab c b | cB b | ab Cc B b | ab c B b ,
B  c | ab Cc | ab c | cB | ab Cc B | a b c B ,
C  ab C | ab ,
B  bAc | bc | bAc B | bc B ,
b  b,
c  c }.
IB102 ­ úkol 10 ­ řešení Odevzdání: 8. 12. 2008
Vypracoval: James Bond UČO: 007
Skupina: MI6
2. [2 body] Nechť L = {ai
bj
| i, j  N0; ki = lj; k, l  {1, 2}}. Zkonstruujte zásobníkový
automat A akceptující prázdným zásobníkem jazyk L.
Řešení: Hledaný automat je A = ({q0, qA1, qA2, qE, qB, qF }, {a, b}, {Z0, B}, , q0, Z0, ), kde
(qF , , Z0) = {(qF , )}
(q0, , Z0) = {(qF , )}
(q0, a, Z0) = {(qA1, BZ0), (qE, BZ0), (qB, BBZ0)}
(qA1, a, B) = {(qA2, B)}
(qA2, a, B) = {(qA1, BB)}
(qE, a, B) = {(qE, BB)}
(qB, a, B) = {(qB, BBB)}
(x, b, B) = {(qF , )} x  {qF , qA2, qE, qB}
Základní myšlenka konstrukce je, že v zásobníku počítáme, kolik znaků b ještě musíme zapsat.
Ještě předtím při načítaní prvního a nedeterministicky rozhodneme, jestli bude více áček,
více béček, nebo obou stejně (Pomocí stavů qA1, qB, qE). Každý z podprogramů ukládá na
zásobník správný počet symbolů podle načtených áček.
Po načítání prvního béčka projdeme z podprogramu do stavu qF . Tady ze zásobníku symboly
odebíráme pro každé načtené b. Pokud je na zásobníku jenom iniciální symbol, znamená to,
že sme načetli celé správné slovo a akceptujeme vyprázdněním zásobníku.