IB102 - úkol 10
Odevzdání: 6.12. 2010
Vypracoval(a): UCO: Skupina:
1. [2 body] Mejme gramatiku G = ({S, X, Y, Z}, {a, b, c}, P, S), kde
P = {   S XZX,
X — Xbc | Ybc,
Y —  aa | Saa,
Z —  ZZb | c }.
Ke gramatice G sestrojte (použitím algoritmu z prednašky) ekvivalentní gramatiku v Grei-bachove normainí forme.
IB102 - úkol 10
Odevzdání: 6.12. 2010
Vypracoval(a): UCO: Skupina:
2. [3 body] O následujících jazycích rozhodnete, zda jsou bezkontextove, a sve rozhodnutí dokazte. (V prípade, ze jazyk je bezkontextová, nám bude jako důkaz stacit napsání prísluSne bezkontextove gramatiky nebo zasobníkoveho automatu.)
(a) Li = {w | w E {a, b}+, #0(w) = #b(w)}2
(b) L2 = {w2 | w E {a, b}+, #a(w) = #b(w)}