IB102 – úkol 9, příklad 2 Odevzdání: 2. 12. 2013
Vypracoval(a): UČO:
Skupina:
2. [2 body] Nechť Σ = {a, b} je abeceda a L, R ⊆ Σ∗
libovolné 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) Pokud jazyk R je regulární a jazyk L je rekursivně spočetný, pak jazyk L \ R je
rekursivně spočetný.
(b) Pokud jazyk L je bezkontextový, pak jazyk {w#w | w ∈ L} ⊆ (Σ∪{#})∗
je rekursivní.
Možná se vám bude hodit následující tvrzení, jehož platnost nemusíte dokazovat.
• Jazyk {w#w | w ∈ Σ∗
} ⊆ (Σ ∪ {#})∗
je rekursivní.
1