IB102 – úkol 5, příklad 1 – řešení Odevzdání: 21. 10. 2013
Vypracoval(a): UČO:
Skupina:
1. [2 body] Tento úkol se skládá ze 3 nezávislých podúkolů:
a) Nechť R1, R2 jsou regulární jazyky nad abecedou Σ = {a, b} a platí R1 ⊆ R2.
Rozhodněte a dokažte, zda libovolný jazyk L, pro který platí R1 ⊆ L ⊆ R2, je také
regulární. [0.5 bodu]
b) Označme P třídu všech jazyků nad abecedou Σ = {a, b}, které obsahují alespoň
jedno slovo sudé délky. Rozhodněte a dokažte, zda je třída P uzavřená na následující
operace:
• průnik,
• sjednocení,
• doplněk,
• rozdíl,
• zřetězení,
• mocnina (libovolná, včetně 0),
• iterace.
Pro každou uvedenou operaci buďto dokažte, že je na ni třída P uzavřená, nebo
uveďte konkrétní protipříklad. [1 bod]
c) Uvažme libovolný jazyk X, který není kontextový, libovolný regulární jazyk R a
libovolný ko-konečný jazyk K (jazyk je ko-konečný, je-li jeho doplněk konečný).
Dále uvažme jazyk L definovaný následovně:
L = (R \ (co-K ∩ X))∗
Rozhodněte a dokažte, zda je jazyk L regulární. [0.5 bodu]
a) Tvrzení neplatí.
Důkaz. Najdeme protipříklad, tj. jazyky R1, R2, L, pro než tvrzení neplatí. Uvažme
R1 = ∅ (prázdný jazyk) a R2 = Σ∗
(jazyk všech slov nad abecedou Σ). Oba tyto
jazyky jsou regulární a zjevně také R1 ⊆ R2. Neregulární jazyk vyhovující zadání je
pak například jazyk L = {an
bn
| n ∈ N} (důkaz neregularity viz například skripta,
příklad 2.15). Nalezli jsme tedy protipříklad a tedy tvrzení v obecnosti neplatí.
b) Uvažme postupně všechny operace ze zadání:
• Třída P není uzavřená na průnik.
Důkaz. Uvažme jazyky L1 = {a, ab} a L2 = {a, aa}. Zjevně L1, L2 ∈ P.
Průnikem získáme jazyk L1 ∩ L2 = {a}, který již ale nepatří do třídy P.
1
IB102 – úkol 5, příklad 1 – řešení Odevzdání: 21. 10. 2013
Vypracoval(a): UČO:
Skupina:
• Třída P je uzavřená na sjednocení.
Důkaz. Uvažme libovolné 2 jazyky L1, L2 ∈ P. Potom z definice P existuje
nějaké slovo w ∈ L1, které je sudé délky. Jelikož ale L1 ⊆ (L1 ∪ L2), pak také
w ∈ (L1 ∪ L2) a tedy L1 ∪ L2 ∈ P.
• Třída P není uzavřená na doplněk.
Důkaz. Uvažme jazyk L = Σ∗
\ {a}. Zjevně aa ∈ L a tedy L ∈ P. Doplňkem
získáme jazyk co-L = {a}, který již ale nepatří do třídy P.
• Třída P není uzavřená na rozdíl.
Důkaz. Uvažme jazyky L1 = {a, aa} a L2 = {aa}. Zjevně L1, L2 ∈ P. Rozdílem
získáme jazyk L1 \ L2 = {a}, který již ale nepatří do třídy P.
• Třída P je uzavřená na zřetězení.
Důkaz. Uvažme libovolné 2 jazyky L1, L2 ∈ P. Potom z definice P existují
nějaká slova w1 ∈ L1 a w2 ∈ L2, která jsou sudé délky. Jelikož ale w1.w2 ∈
L1.L2, pak také L1.L2 ∈ P, protože slovo w1.w2 je sudé délky.
• Třída P je uzavřená na mocninu.
Důkaz. Uvažme libovolný jazyk L ∈ P. Potom z definice P existuje nějaké
slovo w ∈ L, které je sudé délky. Pak platí, že wk
má sudou délku a wk
∈ Lk
pro každou mocninu k ≥ 0. Třída P je tedy uzavřena na mocninu.
• Třída P je uzavřená na iteraci.
Důkaz. Uvažme libovolný jazyk L ∈ P. Z definice iterace zjevně platí L ⊆ L∗
.
Jelikož L ∈ P, obsahuje L alespoň jedno slovo sudé délky. Pak ale L∗
obsahuje
také alespoň jedno slovo sudé délky a tedy L∗
∈ P.
c) Tvrzení platí.
Důkaz. Důkaz je složen z následujících 5 pozorování:
• Jazyk K je ko-končný, jazyk co-K musí tedy být konečný.
• Průnik konečného jazyka s jakýmkoliv jiným jazykem je vždy konečný, tedy
jazyk co-K ∩ X musí být konečný.
• Každý konečný jazyk je regulární, jazyk co-K ∩ X je tedy regulární.
• Regulární jazyky jsou uzavřeny na rozdíl, jazyk R\(co-K∩X) je tedy regulární.
• Regulární jazyky jsou uzavřeny na iteraci, jazyk (R \ (co-K ∩ X))∗
je tedy
regulární.
2