IB005 úkol 12, příklad 1 Odevzdání: 16. 5. 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.
1. [0,5 bodu] Nechť L, R jsou jazyky nad abecedou Σ = {0, 1, #}.
O každém z následujících tvrzení rozhodněte, zda je pravdivé, a vaše tvrzení dokažte.
a) Jazyk L je DCFL, jazyk R je regulární =⇒ jazyk co−L ∩ co−R je DCFL.
b) Jazyk L je CFL a jazyk R je rekurzivně spočetný =⇒ jazyk (L ∩ R) je rekurzivní.
c) Jazyk L ∩ co−R je CFL, L je nekonečný CFL =⇒ R je regulární.
d) Jazyk R je CFL, co−L je rekurzivní =⇒ L ∩ co−R je rekurzivní.
e) Jazyk L je CFL =⇒ embrace(L) je CFL.
Operace embrace uzávorkuje slova daného jazyka kulatými nebo hranatými závorkami. Formálně
bychom ji definovali následovně:
embrace(L) = {awb | w ∈ L, a ∈ {[, (}, b ∈ {], )}, a = [⇔ b =]}
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.