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).
Jazyk L je regulární, dokážeme to například tak, že pro něj zkonstruujeme odpovídající regulární
gramatiku. Při její konstrukci je vhodné si návodně pojmenovat neterminální symboly, protože nám
budou napomáhat uvědomit si, jaké vzory jsou povoleny. Pod vzory myslíme možné posloupnosti
písmen mezi dvěma výskyty znaku b, tedy bb, bab, nebo baab, protože podmínka v definici L je
kladena právě na počet a mezi dvěma bezprostředně následujícími b. Pro každé slovo je příslušný
vzor dán jednoznačně vzdáleností prvních dvou b.
Nejprve zaručíme, aby každé slovo mohlo začínat (S) nebo končit (A) libovolným množstvím
znaků a. Jinak je základní myšlenka konstrukce v tom, že od prvního výskytu b zaznamenáme vzor
(B). Jakmile máme zafixovaný vzor, musíme zajistit, aby v daném slově již nebylo možné použít jiný
vzor (C). Kromě toho musíme dávat pozor, abychom neporušili požadavky na regulární gramatiky,
speciálně to, kdy je možno přepsat S na ε (vytvoříme pomocný neterminál S ).
Nechť tedy G = ({S, S , Bb, Bba, Bbaa, Cbb, Cbab, Cbaba, Cbaab, Cbaaba, Cbaabaa, A}, Σ, P, S), kde
P = {S → aS | bBb | a | b | ε,
S → aS | bBb | a | b,
Bb → bCbb | aBba | a | b,
Bba → bCbab | aBbaa | a | b,
Bbaa → bCbaab | aA | a | b,
Cbb → bCbb | aA | a | b,
Cbab → aCbaba | a,
Cbaba → bCbab | aA | a | b,
Cbaab → aCbaaba | a,
Cbaaba → aCbaabaa | a,
Cbaabaa → bCbaab | aA | a | b,
A → aA | a}.
Platí, že L(G) = L. A protože G je regulární gramatika, jazyk L je také regulární.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.