IB005 úkol 12, příklad 1 Odevzdání: 13. 5. 2024 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.
1. [0,5 bodu] Mějme abecedu Σ = {a, b, c}.
O každém z následujících tvrzení rozhodněte, zda je pravdivé pro všechny jazyky L, R, M nad
abecedou Σ, a svá tvrzení dokažte.
a) L je CF, M je DCF, R je CS =⇒ (L · M) ∩ R je CS
b) L ∪ R není CF =⇒ L není DCF nebo R není DCF
c) L je CF a R je CF =⇒ L \ R je CF
d) L má regulární podmnožinu, co−L je RE =⇒ L je Rec
Mohou se vám hodit známé jazyky a uzávěrové vlastnosti z přednášky, cvičení a ze skript. Pokud
použijete tyto jazyky, nemusíte dokazovat jejich vlastnosti deklarované na přednášce/cvičení/ve
skriptech, ale musíte se odkázat na místo, odkud je berete. Podobně uzávěrové vlastnosti známé
z přednášky/cvičení/skript 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; tedy v případě příslušnosti
jazyka do dané třídy sestrojit příslušnou gramatiku/TS/automat, a v případě nepříslušnosti dokázat
např. pomocí PL. Nemusíte dokazovat, že vaše gramatika/automat/TS generuje/rozpoznává chtěný
jazyk. Všechny podpříklady by měly být řešitelné bez PL, ale klidně ho použijte, pokud vám pomůže.
Pokud dokazujete, že tvrzení neplatí, udejte konkrétní protipříklad (tedy jazyky L, R a M,
t.ž. tvrzení pro ně neplatí).
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.