IB102 úkol 9, příklad 1 Odevzdání: 26. 11. 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] Uvažte jazyk L nad abecedou Σ = {a, b} 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 bezkontextový, a své tvrzení dokažte.
Tedy je-li vaše odpověď kladná, tj. že se jedná o bezkontextový jazyk, uveďte příslušnou bezkontextovou
gramatiku nebo zásobníkový automat včetně všech formálních náležitostí. Pokud se podle
vás naopak o bezkontextový jazyk nejedná, dokažte tuto skutečnost pomocí Lemmatu o vkládání pro
bezkontextové jazyky (Pumping lemma pro CFL).
Poznámka: Pro tento úkol definujeme vzdálenost mezi dvěma bezprostředně po sobě následujícími
znaky b jako počet znaků různých od b mezi nimi. Například vzdálenost mezi prvním b a posledním
b ve slově baaab je 3.
Pomocí Lemmatu o vkládání ukážeme, že se nejedná o bezkontextový jazyk. Postupujeme těmito
kroky:
• Nechť n ∈ N je libovolné.
• Zvolme z = banban+1ban+2b. Platí, že z ∈ L a |z| = 3n + 7 > n.
• Nechť uvwxy = z je libovolné rozdělení slova z takové, že vx = ε a |vwx| ≤ n.
• Ukážeme, že existuje i ∈ N0 takové, že uviwxiy ∈ L.
Rozlišme následující případy, které mohou pro rozdělení slova z nastat:
1) vx obsahuje znak b. Pak právě jedno z v, x obsahuje právě jedno b, protože |vwx| ≤ n a mezi
každými dvěma b ve slově z je minimálně n znaků a. Nechť podslovo v obsahuje znak b (pro
x bychom postupovali symetricky), podslovo v je tedy tvaru v = akbal, kde k, l >= 0. Zvolme
i = 3, pak slovo z = uv3wx3y obsahuje tři výskyty znaku b v jeho podslově v3 = akbal+kbal+kbal,
vzdálenost mezi prvním a druhým a mezi druhým a třetím z těchto 3 výskytů b je stejná, tedy
z /∈ L.
2) vx neobsahuje b, tedy vx = ak. Pak vwx nemůže zasahovat do všech třech podslov an, an+1, an+2,
protože |vwx| ≤ n a tedy určitě nemůže zasahovat zároveň do an i an+2, protože je mezi nimi
n + 3 znaků.
Pokud vx nezasahuje do an, pak zvolíme i = 0.
• Pokud vx zasahuje do an+1, porušili jsme nerovnost mezi první a druhou skupinou a.
• Pokud vx nezasahuje ani do an+1, musí zasahovat do an+2 a porušili jsme nerovnost mezi
druhou a třetí skupinou a.
Pokud vx nezasahuje do an+2, pak zvolme i = 2.
• Pokud vx zasahuje do an+1, porušili jsme nerovnost mezi druhou a třetí skupinou a.
• Pokud vx nezasahuje ani do an+1, musí zasahovat do an a porušili jsme nerovnost mezi
první a druhou skupinou a.
Pro všechna platná rozdělení jsme tedy nalezli i ∈ N0, pro které slovo uviwxiy nepatří do jazyka L.
Díky Lemmatu o vkládání pro bezkontextové jazyky tak víme, že jazyk L není bezkontextový.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.