IB005 úkol 3, příklad 2 Odevzdání: 21. 3. 2021 23:59
Jméno: UČO:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
2. [0,5 bodu] Mějme jazyk L = {akbl | k, l ≥ 0, pokud k je liché, pak l je prvočíslo }.
Jazyk L není regulární. Dokažte, že neregularitu jazyka L nelze dokázat pomocí formulace věty
o vkládání ze skript. Jinými slovy: nalezněte takové n, že pro každé w ∈ L délky alespoň n existuje
x, y, z ∈ {a, b}∗ takové, že xyz = w, |xy| ≤ n, y = ε a pro každé i ≥ 0 platí: xyiz ∈ L. Dokažte, že
n má uvedené vlastnosti.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.