IB102 úkol 1, příklad 2 Odevzdání: 24. 9. 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.
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é odpovídajícím způsobem.
a) {a, b}+ bez použití iterace (∗) a pozitivní iterace (+)
b) ({a}∗ \ Σ) bez použití doplňku (co−) a rozdílu (\)
c) jazyk tvořený právě slovy s lichým počtem znaků a
d) {aa, b}∗ ∩ {a, bb}∗ bez použití průniku (∩)
Pro každou část této úlohy uvedeme jedno z možných řešení.
a) Jediné slovo, které jazyk {a, b}+ neobsahuje, je prázdné slovo, proto lze tento jazyk zapsat jako
doplněk jazyka obsahujícího prázdné slovo: {ε}. Ten sice v nabídce nemáme, ale můžeme jej
vyjádřit pomocí nulté mocniny:
La = {a, b}+
= co− {a}0
.
b) Po odečtení abecedy {a, b} bude výsledný jazyk obsahovat prázdné slovo a slova tvořená dvěma
a více znaky a:
Lb = ({a}∗
\ Σ) = {a} · {a}+
∪ {a}0
.
c) V jazyce budou (mimo jiné) všechna slova obsahující právě jeden znak a:
Lc1 = {b}∗
· {a} · {b}∗
.
Pokud po prvním znaku a následují ještě další znaky a, zajistíme jejich výsledný lichý počet tím,
že dovolíme rozšiřovat slovo vždy právě o dva znaky a. Na počtech znaků b mezi nimi nezáleží:
Lc = {b}∗
· {a} · {b}∗
· ({a} · {b}∗
· {a} · {b}∗
)∗
.
d) První iterace umožňuje tvořit pouze slova, kde se vyskytují znaky a ve dvojicích, nikdy samostatně
(na znacích b nezáleží), obdobně druhá iterace jenom slova s dvojicemi znaků b. Jejich průnikem
tedy bude jazyk slov tvořených libovolným počtem zřetězení dvojic aa a bb:
Ld = {aa, b}∗
∩ {a, bb}∗
= ({a}2
∪ {b}2
)∗
.
Alternativně můžeme využít De Morganova pravidla:
Ld1 = {a}2
∪ {b}
∗
,
Ld2 = {a} ∪ {b}2 ∗
,
Ld = co−(co−Ld1 ∪ co−Ld2).
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.