IB102 - úkol 2 - řešení
Odevzdání: 4.10. 2010
Vypracoval: James Bond UCO: 007
Skupina: MI6
1. [3 body] Na obrázku mate 2 Čtverce, v kazdem z nich 9 jazyku nad abecedou (a,6}. V sousedních sloupcích spojte carou ty jazyky, mezi kterámi je relace inkluze (tzn. levá jazyk je podmnozinou praveho jazyka anebo jsou si rovny). U jazyku, které se vam nepodarí s nicím spojit, strucne vysvetlete proc.
Poznámka: Zatímco v levem ctverci jsou konkrétní jazyky, v pravem jsou vsechny jazyky odvozene od jazyka L, kterí není specifikovan. Do praveho ctverce proto zaznacte inkluze, které platí obecne, tj. pro libovolnou volbu jazyka L C (a, 6}*. U jazyku z praveho ctverce, kteríe nejsou s nicíím spojeny, by proto melo vysvetleníí vyuzíívat protiprííklady.
CC
L11 L12 L13
L21 J       L 22       \^ L 23
L31 L32 L33
L41
CC
L42 L43
L5V
L52 L53 •-•
L61 \L62/ L63
L11
L21 L31
L12 L22 L32
L13 L23 L33
(a,6}* (a}
(ab, a66}
(a}.(6}+
(a}+
(6}+
co—(a, 6}*
(a}*
(a}+.(6}+
L41 — LR L51 — L
L61 — (L0 U (a, 6})+
L42 — L. (LR)* L52 — L6
L62 — L U L0 L43 — L U L (LR)+
L53 — L*
L63 — co—L n L
Řešení: Relace inkluze je zakreslena v obrazku výse. jsou níasledujíícíí:
Zduvodnení s nicím nespojeních jazyku
• Lii je jazyk všech slov nad abecedou {a, b}*. Obsahuje tedy i např. slovo ba, které nepatří do zadneho z jazyku Li2, L22 a L32.
• L32 obsahuje např. slovo b, ktere nepatří do žádneho z jazyku L13, L23 a L33. Zaroven do L32 nepatří ani slovo a, ani slovo ab, není tedy nadmnozinou L11, L21 (kvůli a) ani L31 (kvuli ab).
• L13 je přázdná jazyk. Jazyky L12, L22 a L32 jsou ale nepřazdne, nemohou bát přoto jeho podmnozinou.
• L41 je zřcadlová obřaz jazyka L. Zvolíme-li např. L = {ab}, pak L41 = {ba}. Slovo ba pak ovsem neobsahuje zadná z jazyku L42 = {ab}.{ba}*, L52 = {abababababab} a Lg2 = {e,ab}.
• L61 je (přo libovolnou volbu jazyka L) jazyk vsech slov. StaCí tedy zvolit např. L = 0, pak zřejme L42 = 0, L52 = 0, L62 = {e}. Zádná z techto jazyku zřejme není nadmnozinou jazyka vsech slov.
• L63 je (přo libovolnou volbu jazyka L) přazdná jazyk. Stacá za L zvolit libovolná nepřazdná jazyk, pak zřejme i jazyky L42, L52 a L62 jsou nepřázdne a nejsou tedy podmnozinami přázdneho jazyka.
IB102 - úkol 2 - řešení
Odevzdání: 4.10. 2010
Vypracoval: James Bond UCO: 007
Skupina: MI6
2. [3 body] Mejme jazyk L = (ab, ba, aba} nad abecedou S = (a, b}. Zjistěte, kolik slov ma nasledujúci jazyk:
co- ((co-L)2)
Odpoveď zduvodnete.
Řešeni: Jazyk co— ((co—L)2) ma práve jedno slovo, a to aba. Ukážeme, ze jazyk (co—L)2 obsahuje všechna slova ze S* krome slova aba. Necht' tedy w E S*. Mame nasledujúci ctyfí pripady:
• w nepatri do L. Pak w patri do co—L. Protoze rovnez e patri do co—L, dohromady tedy w = w • e E (co—L)2.
• w = ab. Slova a a b nepatri do L, patri proto do co—L. Potom w = a • b E (co—L)2.
• w = ba. Podobne jako v predchozim bode w = b • a E (co—L)2.
• w = aba. Neni zidni moznost, jak rozdelit w na dve slova tak, aby obe byla v co—L. To se snadno overi, nebot' mozni rozdeleni jsou pouze ctyri (e • aba, a• ba, ab• a, aba • e). Proto w E (co—L)2.
Ukazali jsme tedy, ze jazyk (co—L)2 obsahuje vsechna slova ze S* krome slova aba. Proto pro jeho doplnek plati co— ((co—L)2) = (aba}.