IB102 – úkol 3, příklad 2 Odevzdání: 7. 10. 2013
Vypracoval(a): UČO:
Skupina:
2. [2 body] Uvažme jazyk
L = ai
bj
ck
| i, j, k ≥ 0, pokud i = 1, pak j = k
Dokažte pomocí Myhill-Nerodovy věty, že jazyk L není regulární.
Bonus: [+2 body] Dokažte, že neregularitu jazyka L nelze dokázat pomocí Lemmatu
o vkládání. Jinými slovy: nalezněte takové n, že pro každé w ∈ L délky alespoň n existuje
x, y, z takové, že xyz = w, |xy| ≤ n, y = ε a pro každé i ≥ 0 platí: xyi
z ∈ L. Dokažte, že
n má uvedené vlastnosti.
1