IB102 úkol 12, příklad 1 Odevzdání: 17. 12. 2018
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] Nechť Σ je libovolná abeceda a R, L1, L2, D1, D2 jsou jazyky nad touto abecedou.
O každém z následujících tvrzení rozhodněte, zda je pravdivé, a vaše tvrzení dokažte.
a) Jazyk R je regulární =⇒ jazyk {anbncn | n > 0} ∩ ({c}+ · R) je bezkontextový.
b) Jazyk (L1 ∪ L2) není bezkontextový =⇒ jazyk L1 není bezkontextový nebo jazyk L2 není
bezkontextový.
c) Jazyk D1 je deterministický bezkontextový a jazyk R je regulární =⇒ jazyk co−(D1 ∪ R) je
bezkontextový.
d) Jazyky D1 a D2 jsou deterministické bezkontextové =⇒ jazyk (co−D1) \ D2 je 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.