IB005 úkol 12, příklad 1 Odevzdání: 14. 5. 2023 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] Mějme abecedu Σ = {0, 1, #}.
O každém z následujících tvrzení rozhodněte, zda je pravdivé pro všechny jazyky L, R nad abecedou
Σ, a svá tvrzení dokažte.
a) Jazyk L není rekurzivně spočetný =⇒ co−L není rekurzivně spočetný.
b) Jazyk L není CSL =⇒ jazyk L je nekonečný.
c) Jazyk L je DCFL a jazyk R je CFL =⇒ L ∪ R je DCFL.
d) Jazyk L je CFL =⇒ co−L je rekurzivně spočetný.
Mohou se vám hodit známé jazyky a uzávěrové vlastnosti z přednášky a cvičení. Pokud použijete tyto
jazyky, nemusíte dokazovat jejich vlastnosti deklarované na přednášce/cvičení. Podobně uzávěrové
vlastnosti známé z přednášky/cvičení nemusíte dokazovat. Pokud naopak použijete jazyky, jejichž
vlastnosti nebyly deklarovány na přednášce/cvičení, musíte tyto vlastnosti dokázat.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.