IB 102 — úkol 1, příklad 2 — řešení
Odevzdání: 24. 9. 2012
Vypracoval: James Bond Skupina: MI6
UCO: 007
2. [2 body] Nechť L je jazyk nad abecedou E = {a, b} tvořený právě všemi slovy která mají lichý počet znaků a zároveň se ve slovech nevyskytují 2 znaky a za sebou (tedy mezi každými dvěma výskyty znaku a je alespoň jeden znak b).
Zapište jazyk L pomocí jednoprvkových jazyků {a} a {&} s využitím konečného počtu operací sjednocení (U), průniku (fl), rozdílu (\), doplňku (co—), zřetězení (•), mocniny (2,3,...), iterace (*) a pozitivní iterace (+).
Řešeni: Pro zpřehlednění zápisu si nejprve definujeme následující jazyky. Jazyk L\ bude obsahovat všechna slova s lichým počtem znaků, jazyk L2 bude obsahovat všechna slova ve kterých se nevyskytují 2 znaky a za sebou (jakožto doplněk k jazyku, který obsahuje všechna slova, ve kterých se vyskytují alespoň 2 znaky a za sebou).
Li = (W U {b}) ■ (({a} U W) • ({a} U {b}))* L2 = co-(({a} U {b})* ■ {a} • {a} • ({a} U {b})*)
Řešení pak můžeme snadno zapsat jako průnik obou jazyků takto: L = L\ fl L2, neboli
L = ({a} U {b}) ■ (({a} U {b}) • ({a} U {b}))* n co-(({a} U {b})* • {a} • {a} • ({a} U {b})*)