IB102 – úkol 1, příklad 1 Odevzdání: 22. 9. 2014
Vypracoval(a): UČO:
Skupina:
1. [2 body] Mějme abecedu Σ = {a, b}. O následujících výrazech rozhodněte, zda určují
jazyky nad abecedou Σ. Pokud ne, napište proč. Pokud ano, rozhodněte, zda jsou tyto
jazyky konečné. Konečné jazyky zapište jako množinu slov (tedy množinu posloupností
znaků). Pro nekonečné jazyky napište 2 slova, která do jazyka patří, a 2, která do něj
nepatří.
a) {a}∗
b) {b3
} ∪ a∗
c) ({aa, ab} · {b})2
d) ({aa, ab} ∪ {b})2
e) ∅∗
∪ ({a} · {b, a})
f) {a, b, ab}∗
∩ ∅+
g) co−({a2
, b}∗
)
h) {a, b}∗
· a · {a, b}∗
Za zadání ručí ib102-du@fi.muni.cz 1