IB102 – úkol 1, příklad 2 – řešení Odevzdání: 22. 9. 2014
Vypracoval(a): UČO:
Skupina:
2. [2 body] Mějme abecedu Σ = {a, b}.
Každý z následujících jazyků popište pomocí jednoprvkových jazyků {a} a {b} s využitím
konečného počtu operací sjednocení (∪), průniku (∩), rozdílu (\), doplňku (co−), zřetězení
(·), mocniny (0
, 2
, 3
, . . .), iterace (∗
) a pozitivní iterace (+
), mimo operací, které jsou
zakázány u konkrétního jazyka. Navíc můžete používat pomocné jazyky rovněž zadefinované
tímto způsobem.
a) {a, b}+
bez použití pozitivní iterace
b) co− ({aa}∗
) bez použití doplňku a rozdílu
c) {ε} bez použití mocniny a rozdílu
d) co−{a} · co−{b} bez použití doplňku a rozdílu
Nejdříve si pro lepší srozumitelnost zápisu řešení zadefinujeme pomocné jazyky:
• Lab = {a, b} = {a} ∪ {b}
• Lempty = ∅ = {a} ∩ {b}
• Laa = {aa} = {a} · {a}
Nyní můžeme pomocí povolených operací a pomocných jazyků zapsat jednotlivá řešení:
a) {a, b}+
= Lab · L∗
ab
Je zřejmé, že pomocí L∗
ab vygenerujeme všechna slova nad abecedou Σ. Přiřetězením
jazyka Lab se zbavíme prázdného slova, které požadovaný jazyk {a, b}+
neobsahuje,
zároveň však všechna ostatní slova zachováme.
Další možné řešení je například {a, b}+
= L∗
ab \ L∗
empty.
b) co− ({aa}∗
) = (L∗
ab · {b} · L∗
ab) ∪ ({a} · L∗
aa)
První závorka vygeneruje všechna slova obsahující alespoň jedno b a druhá závorka
vygeneruje právě slova obsahující lichý počet písmen a a žádné b.
c) {ε} = L∗
empty
Řešení plyne přímo z definice.
d) co−{a} · co−{b} = L∗
ab
Jedná se o jazyk obsahující všechna slova nad abecedou Σ. Je potřeba si dobře uvědomit,
že jazyk co−{a} skutečně obsahuje všechna slova nad Σ (včetně ε) kromě slova
a. Obdobně pro jazyk co−{b}.
Definice zřetězení aplikovaná na naše jazyky vypadá následovně:
co−{a} · co−{b} = {u · v | u ∈ co−{a} ∧ v ∈ co−{b}}
Nyní je zřejmě vidět, že pro u = ε ∈ co−{a} se do výsledku vygeneruje co−{b}, tedy
všechna slova až na b. To ovšem dostaneme pro u = b ∈ co−{a} ∧ v = ε ∈ co−{b}.
Celkově tedy dostáváme L∗
ab.