IB005 úkol 13, příklad 1 Odevzdání: 30. 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}.
Uvažme operaci killSuffixes(L, u) = {w ∈ L | w nezačíná na neprázdný suffix u} (neprázdný suffix
je suffix různý od ε).
Formálně definujeme operaci killSuffixes(L, u) následovně:
killSuffixes(L, u) =
L \ ({u} · Σ∗) pro u ∈ Σ
killSuffixes(L, w) \ ({u} · Σ∗) pro u = xw, x ∈ Σ, w ∈ Σ∗
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 DCFL a jazyk L3 je DCFL =⇒ jazyk (co−(L2 ∩ L3)) · L1 je CFL.
b) Neexistuje Turingův stroj, který rozhoduje L1 =⇒ L1 není rekurzivně spočetný nebo co−L1
není rekurzivně spočetný.
c) Jazyk L1 je DCFL a jazyk L2 je DCFL =⇒ jazyk co−(L1 \ L2) je DCFL.
d) L1 je kontextový a w ∈ Σ∗ =⇒ killSuffixes(L1, w) je kontextový.
V řešení můžete využívat tvrzení o uzávěrových vlastnostech i tvrzení o příslušnosti konkrétního
jazyka do některé třídy, pokud byla dokázána na přednášce nebo na cvičení. Pokud se v řešení
opřete o tvrzení, které dokázáno nebylo, ať už se jedná o tvrzení o jazyku nebo uzávěrové vlastnosti,
musíte dané tvrzení dokázat sami.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.