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.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.