IB102 úkol 4, příklad 2 Odevzdání: 15. 10. 2018
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. [2 body] Mějme abecedu Σ = {a, b}. Rozhodněte, zda je jazyk
L = {w ∈ {a, b}∗
| vzdálenosti mezi každými dvěma po sobě bezprostředně následujícími b ve
slově w jsou všechny vzájemně různé}
regulární a své tvrzení dokažte. Tedy pokud se podle vás jedná o regulární jazyk, uveďte příslušnou
regulární gramatiku nebo konečný automat včetně všech formálních náležitostí. Pokud se podle vás
naopak o regulární jazyk nejedná, dokažte tuto skutečnost pomocí Myhillovy-Nerodovy věty.
Jazyk L není regulární. Důkaz provedeme pomocí Myhillovy-Nerodovy věty (konkrétně z tvrzení
„Relace ∼L má nekonečný index =⇒ L není rozpoznatelný deterministickým konečným automatem“).
Tedy chceme dokázat, že ∼L má nekonečný index.
Důkaz. Uvažme slova ve tvaru wx = baxb, kde x ∈ N0. Ukážeme, že žádná dvě nepatří do stejné
třídy rozkladu podle ∼L.
Pokud k libovolným dvěma slovům wi = baib, wj = bajb, kde i, j ∈ N0, i = j přiřetězíme slovo
aib, tak baibaib ∈ L, ale bajbaib ∈ L. Tedy wi ∼L wj.
Z toho vyplývá, že každé ze slov wx, x ∈ N0 patří do samostatné třídy rozkladu podle ∼L. Tříd
rozkladu je tedy alespoň tolik, kolik přirozených čísel. Relace ∼L tedy nemá konečný index, což
znamená, že L není rozpoznatelný DFA a tedy L není regulární.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.