IB102 – úkol 1, příklad 2 – řešení Odevzdání: 23. 9. 2013
Vypracoval(a): UČO:
Skupina:
2. [2 body] Nechť L je jazyk nad abecedou Σ = {a, b} tvořený právě všemi slovy, která
mají počet znaků a nedělitelný 3 a zároveň se nevyskytují 2 znaky b za sebou (tedy mezi
každými dvěma výskyty znaku b je alespoň jeden znak a).
Zapište jazyk L 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
(2
, 3
, . . .), iterace (∗
) a pozitivní iterace (+
).
Pro přehlednost si nejprve vytvoříme následující 2 pomocné jazyky nad abecedou Σ:
• L1 – jazyk tvořený právě všemi slovy, která mají počet znaků a dělitelný 3
L1 = {b}∗
· {a} · {b}∗
· {a} · {b}∗
· {a} · {b}∗
∗
• L2 – jazyk tvořený právě všemi slovy, kde se nevyskytují 2 znaky b za sebou. Tento
jazyk lze zapsat jako doplněk jazyka právě všech slov obsahujících 2 znaky b za
sebou1
:
L2 = co− {a} ∪ {b}
∗
· {b} · {b} · {a} ∪ {b}
∗
Řešením celého příkladu je potom rozdíl L2 a L1, tedy L = L2 \ L1, neboli:
L = co− {a} ∪ {b}
∗
· {b} · {b} · {a} ∪ {b}
∗
\ {b}∗
· {a} · {b}∗
· {a} · {b}∗
· {a} · {b}∗
∗
Existují i ekvivalentní řešení, například L = co−L1 ∩ L2.
1
Jazyk L2 lze zapsat také bez použití operace doplňku, nicméně zápis je složitější, například:
L2 = {a}+
· {b}
∗
· {a}∗
∪ {b} · {a}+ ∗
· {b} ∪ {b} · {a}+ ∗
vysvětlení: jazyk rozdělíme na 3 podjazyky:
– jazyk všech slov začínajících a (nebo prázdných), kde se nevyskytují 2 znaky b za sebou (pozitivní
iterace {a}+
zajistí, že se bude mezi dvěma znaky b vyskytovat alespoň jeden znak a)
– jazyk všech slov začínajících b, kde se nevyskytují 2 znaky b za sebou a která končí na b
– jazyk všech slov začínajících b (nebo prázdných), kde se nevyskytují 2 znaky b za sebou a která
nekončí na b
1