IB102 úkol 12, příklad 1 Odevzdání: 20. 12. 2019
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. [2 body] Jelikož uzávěrové vlastnosti deterministických bezkontextových jazyků budou odpřednášeny
až v pondělí 16. 12., můžete tento příklad 12. sady odevzdávat do pátku 20. 12. do 12.00.
Datum odevzdání druhého příkladu 12. sady se nemění.
Nechť Σ je libovolná abeceda a R, L1, L2, L3, D jsou jazyky nad touto abecedou, není-li uvedeno
jinak. O každém z následujících tvrzení rozhodněte, zda je pravdivé, a vaše tvrzení dokažte.
a) Jazyk D je deterministický bezkontextový a jazyk R je regulární =⇒ jazyk (co−D \ R) je
deterministický bezkontextový.
b) Jazyk R je regulární nad abecedou {a, b, c} =⇒ jazyk {a#a(w)b#b(w)c#c(w) | w ∈ R} je bezkon-
textový.
c) Jazyk ((L1 ∪ co−L2) · L3) není bezkontextový =⇒ jazyk L1 není bezkontextový nebo jazyk L2
není deterministický bezkontextový nebo L3 není regulární.
d) Jazyk L1 ·L2 není bezkontextový a jazyk L2 je bezkontextový =⇒ jazyk L1 není bezkontextový.
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.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.