IB102 - úkol 9
Odevzdání: 29.11. 2010
Vypracoval(a): UCO: Skupina:
1. [2 body] Mejme následující jazyk:
L = {w e {a, b}* | w = wR} U{w e {a, b}* | #0(w) mod 2 = mod 2}
Sestrojte jednoznačnou bezkontextovou gramatiku generující jazyk L.
IB102 - úkol 9
Odevzdání: 29.11. 2010
Vypracoval(a): UCO: Skupina:
2. [3 body] Mejme gramatiku G = ({S, A, B, C, D, E, F}, {a, b, c}, P, S), kde
{ s	->•	AB | cC,
A	->•	e | aA | SEb,
B	—	e | bB | AEc,
C	—	D | AcB,
D	—	Bb | Abc | C,
E	-	abE | Ec | EF,
F	—	Ea | ba }.
Ke gramatice G sestrojte (použitím algoritmu z prednášky) ekvivalentní gramatiku v Chomskeho normainí forme.
Poznámka: Gramatika v CNF musí bát vždy redukovana.