IB102 úkol 3, příklad 2 Odevzdání: 8. 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] Nechť Σ = {a, b}. Uvažte jazyk L nad Σ takový, že v každém slově je vzdálenost mezi
každými dvěma po sobě bezprostředně následujícími znaky b nejvýše 2 a zároveň jsou tyto vzdálenosti
v rámci každého slova vždy stejné. Tedy například slova aaaaabbb, bab, babab, ε, aaaaaaaaaaa do
jazyka L patří a slova aaaaaabbabaabaaaab, abaaaab, baababa do jazyka L nepatří.
Rozhodněte, zda je L regulární, a své tvrzení dokažte. Tedy je-li vaše odpověď, že se 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í
Lemmatu o vkládání (Pumping lemma).
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.