IB005 úkol 4, příklad 3 Odevzdání: 21. 3. 2022 12:00
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.
3. [0,5 bodu] Rozhodněte, zda existuje jazyk L nad abecedou Σ = {a, b} takový, že:
a) Index ∼L je 3, L je sjednocením dvou tříd rozkladu Σ∗/∼L a zároveň platí, že a ∼L aa, b ∼L bb.
b) Index ∼L je 2 a pro všechna w ∈ L platí |w| = 1.
c) Index ∼L je 5, L je konečný a zároveň platí, že a ≁L b a {a, b} ⊂ L.
Pokud rozhodnete, že jazyk L existuje, uveďte jej. Uveďte také relaci prefixové ekvivalence (∼L)
pro tento jazyk, třídy jejího rozkladu a vyjádřete jazyk L jako sjednocení některých tříd tohoto
rozkladu. Není třeba dokazovat, že uvedená relace ∼L je skutečně ekvivalencí. Obdobně není třeba
dokazovat, že ∼L je prefixovou ekvivalencí pro jazyk L.
Pokud rozhodnete, že jazyk L neexistuje, své tvrzení dokažte.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.