IB005 úkol 5, příklad 1 Odevzdání: 4. 4. 2021 23:59
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. [0,5 bodu] Rozhodněte, zda existuje jazyk L nad abecedou Σ = {a, b} takový, že:
a) L je nekonečný a je sjednocením dvou tříd rozkladu Σ∗/∼L
b) L je konečný, |L| ≥ 3, b ∈ L, aa ∼L aaa, aa ∼L ba
c) Index ∼L je 3 a L je sjednocením 3 tříd rozkladu Σ∗/∼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.