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.
a) platí
Důkaz. Průnik {anbncn | n > 0} ∩ ({c}+ · R) je prázdný, protože každé slovo z jazyka {anbncn |
n > 0} začíná na a ale každé slovo z jazyka ({c}+ · R) začíná na c (pro libovolný R). Dostáváme
tedy „Jazyk R je regulární =⇒ jazyk ∅ je bezkontextový“. Prázdná množina je jistě regulární,
a tedy i bezkontextová, a proto tvrzení platí.
b) platí
Důkaz. Využijeme obměnu tvrzení: „Jazyk L1 je bezkontextový a L2 je bezkontextový =⇒
jazyk (L1 ∪ L2) je bezkontextový.“ To již plyne přímo z toho, že třída bezkontextových jazyků je
uzavřená na sjednocení. Tvrzení tedy platí.
c) platí
Důkaz. Začneme tím, že si upravíme výsledný jazyk: co−(D1 ∪ R) = (co−D1) ∩ (co−R). Dále
jazyk co−D1 je deterministický bezkontextový (DCFL), protože DCFL jsou uzavřeny na doplněk,
a jazyk co−R je regulární, protože regulární jazyky jsou taktéž uzavřeny na doplněk. Jazyk co−D1
je také bezkontextový, protože každý DCFL je také bezkontextový. Bezkontextové jazyky jsou
uzavřeny na průnik s regulárním, a tedy je co−D1 ∩ co−R bezkontextový. Tím pádem tvrzení
platí.
d) neplatí
Důkaz. Opět si upravíme výsledný jazyk: (co−D1) \ D2 = (co−D1) ∩ (co−D2). Nyní stačí vzít
D1 = co−{anbncm | m, n ≥ 1}, D2 = co−{ambncm | m, n ≥ 1}. Jelikož doplňky těchto jazyků
jsou DCFL (viz přednáška), jsou DCFL i tyto jazyky. Pak výsledkem průniku je jazyk {anbncn |
n ≥ 1}, který jistě není ani bezkontextový a tedy nemůže být DCFL. Našli jsme protipříklad,
a tedy tvrzení neplatí.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.