Domácí úkol č. 6
Příklad 1 (8 bodů)
Nechť Σ je libovolná abeceda a L1, L2 ⊆ Σ 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) L1 je deterministický bezkontextový a L2 je regulární =⇒ co-L1 ∩ L2 je
bezkontextový
b) L1 je kontextový a L2 je bezkontextový =⇒ L1 ∪ L2 není bezkontextový
c) L1 je bezkontextový a L2 je rekurzivně spočetný =⇒ L2 \L1 je rekurzivně
spočetný
d) L1 není bezkontextový a L2 je regulární =⇒ L2 \ L1 není bezkontextový
Příklad 2 (5 bodů)
Navrhněte úplný Turingův stroj rozhodující jazyk
L = {w ∈ {a, b, c}∗
| #a(w) = #b(w) = #c(w)}
Příklad 3 (7 bodů)
Navrhněte úplný Turingův stroj rozhodující jazyk
L = {an
. w | w ∈ {0, 1}∗
∧ w je binární zápis čísla n}
1