IB102 – úkol 4, příklad 1 – řešení Odevzdání: 13. 10. 2014
Vypracoval(a): UČO:
Skupina:
1. [2 body]
a) Rozhodněte a zdůvodněte, zda je třída regulárních jazyků nad abecedou Σ = {a, b, c}
uzavřená na unární operaci removeA, která z jazyka odstraní všechna slova obsahující
alespoň jedno a.
b) Dokažte nebo vyvraťte: L je regulární =⇒ L je konečný nebo co−L je konečný
c) Dokažte nebo vyvraťte: L∗
je regulární =⇒ L je regulární
d) Dokažte nebo vyvraťte: L∗
není regulární =⇒ L 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).
a) PLATÍ
Operace removeA se dá zapsat jako removeA(L) = L ∩ {b, c}∗
. Jelikož {b, c}∗
je
regulární jazyk, L je regulární ze zadání a třída regulárních jazyků je uzavřena na
operaci průniku (∩), pak je uzavřena i na operaci removeA.
b) NEPLATÍ
Tato implikace by totiž znamenala, že neexistuje nekonečný regulární jazyk, jehož
doplněk je taky nekonečný. To však můžeme vyvrátit protipříkladem:
Σ = {a}
L = {aa}∗
je nekonečný jazyk, jenž obsahuje jenom slova sudé délky, dokážeme pro
něj jednoduše vytvořit DFA, je tedy určitě regulární.
co−L je nekonečný jazyk, z uzávěrových vlastností regulárních jazyků plyne také
jeho regularita.
Nalezli jsme tedy nekonečný regulární jazyk L, jehož doplněk je také nekonečný,
čímž jsme vyvrátili platnost implikace.
c) NEPLATÍ
Protipříkladem je neregulární jazyk L = {a, b}∪{an
bn
| n ≥ 0}, jehož iterací získáme
jazyk obsahující všechna slova nad danou abecedou, tedy jazyk regulární.
d) PLATÍ
Obměna implikace má tvar: L je regulární =⇒ L∗
je regulární, což triviálně plyne
z uzavřenosti regulárních jazyků na operaci iterace (∗
).