IB102 úkol 6, příklad 1 Odevzdání: 29. 10. 2018
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. [2 body] Nechť K, L a R jsou jazyky nad abecedou Σ = {a, b, c}.
Dokažte nebo vyvraťte každé z následujících tvrzení:
a) Pokud K je konečný jazyk a L je libovolný jazyk, pak (L ∪ co−K) je regulární.
b) Pokud R je regulární a L není regulární, pak (L · R) není regulární.
c) Pokud R je regulární, pak {w | w ∈ R, #a(w) mod 3 = 1} je regulární.
d) Pokud (L \ R)∗ není regulární, pak L není regulární nebo R není regulární.
Pokud budete potřebovat, můžete v celém příkladu využívat toho, že na přednášce a cvičeních byly
ukázány některé neregulární jazyky (jejich neregularitu nemusíte znovu dokazovat). V důkazu můžete
rovněž použít znalosti o uzavřenosti třídy regulárních jazyků na operace prezentované na přednášce.
a) Tvrzení platí.
Důkaz. Výraz (L ∪ co−K) přepíšeme pomocí De Morganových zákonů na co−((co−L) ∩ K).
Třída konečných jazyků je uzavřena na průnik s libovolným jazykem, takže jazyk ((co−L) ∩ K)
je konečný a tedy i regulární. Regulární jazyky jsou uzavřeny na doplněk a tedy i co−((co−L)∩K)
je regulární jazyk.
Poznámka: Pro tento důkaz jsme potřebovali předpoklad, že jazyky L a K jsou nad stejnou abecedou.
Kdyby nebyly, úprava pomocí De Morganových pravidel by nebyla validní. Alternativně
by se pak dal přímo poskytnout protipříklad: K = ∅ nad ΣK = {c}, L = {aibi | i ≥ 0} nad
ΣL = {a, b}.
b) Tvrzení neplatí.
Důkaz. Dokážeme pomocí protipříkladu:
Uvažme regulární jazyk R = ∅ a libovolný neregulární jazyk, například jazyk L = {aibi | i ≥ 0}.
Jejich zřetězením vznikne jazyk L · R = ∅, který je regulární, a tedy implikace neplatí.
c) Tvrzení platí.
Důkaz. Uvažme jazyk P = ({b, c}∗ · {a} · {b, c}∗)3
∗
· {a} · {b, c}∗. Tento jazyk je regulární,
protože vznikl pomocí zřetězení, mocnin a iterací z regulárních jazyků. Pak můžeme jazyk {w |
w ∈ R, #a(w) mod 3 = 1} vyjádřit jako R ∩ P. Takže implikaci můžeme zapsat takto:
R je regulární =⇒ R ∩ P je regulární
Což platí, protože regulární jazyky jsou uzavřeny na průnik.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.
IB102 úkol 6, příklad 1 Odevzdání: 29. 10. 2018
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.
d) Tvrzení platí.
Důkaz. Uvědomme si, že se jedná o implikaci a že obměna implikace zachovává její pravdivostní
hodnotu.
Tedy:
(L \ R)∗
není regulární =⇒ L není regulární ∨ R není regulární
Obměna:
L je regulární ∧ R je regulární =⇒ (L \ R)∗
je regulární
Třída regulárních jazyků je uzavřena na rozdíl i iteraci, takže jazyk (L \ R)∗ je regulární.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.