IB005 úkol 11, příklad 1 Odevzdání: 16. 5. 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] Nechť L1, L2 a L3 jsou jazyky nad abecedou Σ = {a, b, c}.
O každém z následujících tvrzení rozhodněte, zda je pravdivé, a vaše tvrzení dokažte.
a) Jazyk L1 je CFL, jazyk L2 je CFL a jazyk L3 je regulární =⇒ jazyk L∗
1 ·(L2 ∩L3) nemá vlastnost
sebevložení.
b) Jazyk L1 je CFL a jazyk L2 je CFL a n ∈ N =⇒ jazyk (L1 ∪ L2)n je CFL.
c) Jazyk L1 je CFL a jazyk L2 je CFL a n ∈ N =⇒ jazyk {wn | w ∈ L1 nebo w ∈ L2} je CFL.
d) Jazyk (L1 ∪ L2) není CFL a jazyk L1 je CFL =⇒ jazyk co−L2 není regulární.
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.