IB102 ­ úkol 9 Odevzdání: 1. 12. 2008
Vypracoval(a): UČO:
Skupina:
1. [2 body] Následující bezkontextovou gramatiku převedťe do Chomského normální formy
pomocí postupu uvedeného na přednášce:
G = ({S, A, B, C}, {a, b, c}, P, S), kde
P = { S  C | aB | AB,
A  aa | BC | ABC | aAbCc,
B  Ca | C | b,
C   | C | aBc}
IB102 ­ úkol 9 Odevzdání: 1. 12. 2008
Vypracoval(a): UČO:
Skupina:
2. [2 body] Dokažte, že jazyk L = {a(n2)
| n > 0} není bezkontextový. Použijte pumping
lemma pro bezkontextové jazyky.