IB102 úkol 3, příklad 1 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. 1. [2 body] Nechť Σ = {a, b}. Uvažte jazyk L nad Σ takový, že v každém slově se vzdálenosti mezi každými dvěma bezprostředně po sobě následujícími znaky b postupně zvětšují. Tedy například slova babaab, baba, aaaaaabbabaabaaaab, ε do jazyka L patří a slova babab, bbb, abaabab 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). Jazyk L není regulární. Důkaz. Neregularitu jazyka L dokážeme pomocí obměny tvrzení Lemmatu o vkládání. • Nechť n ∈ N je libovolné přirozené číslo, nadále pevné. • Zvolme slovo w = banban+1b. Slovo w jistě patří do jazyka L a jeho délka je |w| = 2n + 4 ≥ n. • Uvažme rozdělení slova w na libovolná slova x, y, z ∈ Σ∗ taková, že jsou splněny následující podmínky: w = xyz, |xy| ≤ n a y = ε. Pak slova x, y, z musí být jednoho z následujících tvarů: (a) x = bak , y = al , z = an−k−l ban+1 b, pro vhodná čísla k ∈ N0, l ∈ N, k + l < n. Zvolme i = 2 a uvažme výsledné slovo xy2z. Dosazením, použitím definice mocniny slova a algebraickými úpravami dostaneme xy2 z = bak · a2l · an−k−l ban+1 b = ban+l ban+1 b. Slovo xy2z jistě nepatří do jazyka L, protože l > 0, a tedy n + l ≥ n + 1. Tedy vzdálenost mezi prvním a druhým znakem b slova w je buď stejná, nebo větší než vzdálenost mezi druhým a třetím znakem b slova w. (b) x = ε, y = bak , z = an−k ban+1 b, pro vhodné číslo k ∈ N0, k < n. Zvolme i = 3 a uvažme slovo xy3z. Dosazením, použitím definice mocniny slova a algebraickými úpravami dostaneme xy3 z = bak bak bak an−k ban+1 b = (bak )2 ban ban+1 b. Slovo xy3z jistě nepatří do jazyka L, protože vzdálenost mezi prvním a druhým znakem b slova w je stejná jako vzdálenost mezi druhým a třetím znakem b slova w. Celkem tedy z obměny Lemmatu o vkládání dostáváme, že jazyk L není regulární. Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.