IB102 – úkol 1, příklad 1 – řešení Odevzdání: 5. 10. 2015
Vypracoval(a): UČO:
Skupina:
1. [2 body] Mějme abecedu Σ = {a, b}.
Pro každé z následujících slov a jazyků:
1. rozhodněte, zda se jedná o slovo, nebo jazyk nad abecedou Σ,
2. pokud se jedná o slovo, napište jej jako posloupnost znaků abecedy, pokud se jedná
o konečný jazyk, napište jej jako množinu slov (tedy množinu posloupností znaků),
pokud se jedná o nekonečný jazyk, napište 2 slova, která do tohoto jazyka patří, a 2,
která do něj nepatří, nebo zdůvodněte, proč žádná taková neexistují.
a) {a}∗
\ {aa, aaa}+
b) ∅0
· {a}0
c) ((ab)2
· ε3
· b)R
d) {abba}2
· ∅+
e) {a · b2
, b3
} · {a}
f) (b2
a)3
· a
g) ({b}+
· {ε}+
) \ {bb}+
h) co−({a}∗
∪ {b}∗
)
a) Výraz {a}∗
\{aa, aaa}+
popisuje konečný jazyk obsahující 2 slova, množinově lze jazyk
zapsat jako {a, ε}.
b) Výraz ∅0
· {a}0
popisuje konečný jazyk {ε}.
c) Výraz ((ab)2
· ε3
· b)R
popisuje slovo bbaba.
d) Výraz {abba}2
· ∅+
odpovídá prázdnému jazyku.
e) Výraz {a · b2
, b3
} · {a} popisuje konečný jazyk obsahující 2 slova, množinově lze jazyk
zapsat jako {abba, bbba}.
f) Výraz (b2
a)3
· a popisuje slovo bbabbabbaa.
g) Výraz ({b}+
· {ε}+
) \ {bb}+
popisuje nekonečný jazyk všech slov bn
, kde n je liché.
Patří do něj tedy například slova b, bbb, nepatří do něj například ε a bb.
h) Výraz co−({a}∗
∪ {b}∗
) popisuje nekonečný jazyk, který obsahuje všechna slova, ve
kterých se vyskytuje zároveň znak a i b. Patří do něj například slova ab a aab, nepatří
do něj například ε a a.