IB102 – úkol 1, příklad 1 – řešení 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}∗
a) Výraz {a}∗
popisuje nekonečný jazyk nad Σ, do kterého patří například slova a a aa,
ale nepatří do něj slova b a ab.
b) Výraz {b3
} ∪ a∗
neurčuje jazyk, jelikož operace iterace není nad slovy definována.
c) Výraz ({aa, ab} · {b})2
odpovídá jazyku 4 slov {aabaab, aababb, abbaab, abbabb}.
d) Výraz ({aa, ab}∪{b})2
popisuje jazyk 9 slov {aaaa, aaab, aab, abaa, abab, abb, baa, bab, bb}.
e) Výraz ∅∗
∪ ({a} · {b, a}) odpovídá jazyku 3 slov {ε, aa, ab}.
f) Výraz {a, b, ab}∗
∩ ∅+
určuje prázdný jazyk, jelikož ∅+
= ∅. Prázdný jazyk je jazykem
nad Σ.
g) Výraz co−({a2
, b}∗
) popisuje nekonečný jazyk obsahující například slova aaa, ab, naopak
do něj nepatří slova b a ε.
h) Výraz {a, b}∗
· a · {a, b}∗
neurčuje jazyk, jelikož operace zřetězení není definována pro
dvojici jazyk a slovo.