IB102 úkol 1, příklad 1 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.
1. [2 body] Mějme abecedu Σ = {a, b}.
Pro každé z následujících slov a jazyků rozhodněte, zda se jedná o slovo, nebo jazyk nad abecedou Σ.
Pokud se jedná o slovo, napište jej jako posloupnost znaků abecedy, pokud se jedná o jazyk, určete,
zda je konečný nebo ne. Dále, 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) {(ab)2
· b}R ∪ ({ε, b} · {b, ba} · {ba})
b) {a}3 · {a, b}∗ ∩ {a, b}∗ · {b}2
c) {a, b, ab}2 · {bb, aa} · ∅+ · {a, b}
d) {ba, aa, a}∗ ∩ {ab, b}∗
e) (aa)R
· (ba)2
f) (Σ∗ \ ∅∗) ∪ {ab}+
g) ({a}∗ \ Σ) ∩ co− {a, b}2 ∗
h) ∅0 · co−(Σ+)
a) Výraz {(ab)2
·b}R odpovídá jazyku {bbaba} a výraz {ε, b}·{b, ba}·{ba} jazyku {bba, baba, bbba, bbaba}
jejich sjednocením vzniká konečný jazyk {bba, baba, bbba, bbaba}.
b) Výraz {a}3 · {a, b}∗ ∩ {a, b}∗ · {b}2 popisuje nekonečný jazyk, který obsahuje slova začínající
alespoň třemi písmeny a a zároveň končící alespoň dvěma písmeny b. Patří do něj například slova
aaabb, aaaabb nepatří do něj například slova a, ε.
c) Výraz {a, b, ab}2 · {bb, aa} · ∅+ · {a, b} odpovídá prázdnému jazyku, protože ∅+ = ∅ a cokoli
zřetězeno s ∅ je opět ∅.
d) Výraz {ba, aa, a}∗ ∩ {ab, b}∗ odpovídá konečnému jazyku {ε}. Neprázdná slova patřící do jazyka
{ba, aa, a}∗ mají za každým písmenem b alespoň jedno písmeno a, nebo obsahují pouze písmena
a. Neprázdná slova patřící do jazyka {ab, b}∗ mají za každým písmenem a alespoň jedno písmeno
b, nebo obsahují pouze písmena b, takže průnik těchto jazyků obsahuje pouze ε.
e) Výraz (aa)R
· (ba)2
vyjadřuje slovo aababa.
f) Výraz (Σ∗ \ ∅∗)∪{ab}+ popisuje nekonečný jazyk, který obsahuje všechny slova kromě ε (protože
∅∗ = {ε}). Takže do něj patří například slova a, b a nepatří do něj jenom slovo ε.
g) Výraz ({a}∗ \ Σ) popisuje jazyk slov, které se skládají pouze z písmen a kromě slova a. Výraz
co− {a, b}2 ∗
popisuje jazyk slov, které mají lichý počet znaků. Jejich průnikem vzniká
nekonečný jazyk, patří do něj například slova aaa, aaaaa a nepatří do něj slova bb, a.
h) Výraz ∅0 · co−(Σ+) popisuje konečný jazyk {ε}. Protože ∅0 = {ε} a co−(Σ+) = {ε} a {ε} · {ε} =
{ε}.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.