IB102 ­ úkol 10 Odevzdání: 8. 12. 2008
Vypracoval(a): UČO:
Skupina:
1. [3 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.
IB102 ­ úkol 10 Odevzdání: 8. 12. 2008
Vypracoval(a): UČO:
Skupina:
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.