IB102 – úkol 1, příklad 2 Odevzdání: 5. 10. 2015
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