IB 102 — úkol 1 — řešení
Odevzdání: 26. 9. 2011
Vypracoval: James Bond UČO: 007
Skupina: MI6
1. [2 body] Mějme následující jazyky nad abecedou E = {a, b}.
Li = ({a} ■ {&}*) • 03 L2 = ({a} U {&})* • 0* £3 = (W* \ {&}) n 0°
Seřaďte zadané jazyky podle počtu slov. Svou odpověď zdůvodněte.
Řešení: Z definice mocniny platí: 0° = {e}, 0n = 0 pro libovolné n > 0, a tudíž 0* = {e}. Jazyky ze zadání je tedy možno upravit následovně:
Lx = ({a} ■ {&}*) • 03 = ({a} • {&}*) -0 = 0 (zřetězení lib. jazyka s 0 je 0)
L2 = ({a} U {b})* ■ 0* = {a, b}* ■ {e} = {a, b}* (zřetězení lib. jazyka s {e} je tentýž jazyk) L3 = ({a}* \ {&}) n 0° = {a}* n {e} = {e}
Vidíme, že jazyk L\ je prázdný, neobsahuje tedy žádné slovo, jazyk L2 obsahuje nekonečně mnoho slov a jazyk L3 obsahuje jedno slovo, slovo e. Pořadí podle počtu slov je tedy následující: Li, L%, L2.
IB 102 — úkol 1 — řešení
Odevzdání: 26. 9. 2011
Vypracoval: James Bond UČO: 007
Skupina: MI6
2. [2 body] Nechť L je jazyk nad abecedou E = {a, b} tvořený právě všemi slovy délky alespoň 5, která mají lichý počet písmen a. Zapište jazyk L pomocí jednoprvkových jazyků {a} a {b} s využitím operací sjednocení (U), průniku (fl), rozdílu (\), doplňku (co—), zřetězení (•), mocniny i2,3,...) a iterace (*).
Řešení je možno napsat například takto:
L = {{b}* ■ {a} ■ {b}* ■ ({a} ■ {b}* ■ {a} • {b}*)*) n (({a} U {b})5 • ({a} U {b})*)
Vysvětleni: první část ({&}* • {a} ■ {b}* ■ ({a} • {b}* ■ {a} ■ {&}*)*) je jazyk všech slov nad zadanou abecedou, která mají lichý počet písmen a. Druhá část (({a} U {b})5 ■ ({a} U {&})*) pak je jazyk všech slov délky alespoň 5. Jejich průnikem pak dostaneme zadaný jazyk L.