IB005 úkol 3, příklad 2 Odevzdání: 14. 3. 2022 12:00
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] Nechť Σ = {a, b, c}. Mějme jazyk L = {w ∈ Σ∗ | druhé písmeno slova w je b nebo
druhé písmeno slova w je c nebo #b(w) < #c(w) }.
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, c}∗ 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.