IB102 – úkol 9, příklad 2 – řešení 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í.
(a) Tvrzení je pravdivé.
Důkaz. Nechť R ⊆ Σ∗
je libovolný regulární jazyk a L ⊆ Σ∗
libovolný rekursivně
spočetný jazyk. Podle Věty 2.51 je třída regulárních jazyků uzavřená na doplňek.
Tudíž jazyk co − R je také regulární a zejména tedy rekursivně spočetný. A protože
třída všech rekursivně spočetných jazyků je uzavřená na průnik (viz slajdy z 10.
přednášky, strana 3), je jazyk
L \ R = L ∩ co − R
rekursivně spočetný.
(b) Tvrzení je pravdivé.
Důkaz. Nechť L ⊆ Σ∗
je libovolný bezkontextový jazyk. Podle Věty 3.58 je třída
bezkontextových jazyků uzavřená na operaci zřetězení. Tudíž jazyk
J = L.{#}.L ⊆ (Σ ∪ {#})∗
je také bezkontextový a zejména tedy rekursivní. A protože třída rekursivních jazyků
je uzavřená na průnik (viz slajdy z 10. přednášky, strana 3), je jazyk
{w#w | w ∈ L} = J ∩ {w#w | w ∈ Σ∗
}
rekursivní.
1