IB102 - úkol 2
Odevzdání: 4.10. 2010
Vypracoval(a): UCO: Skupina:
1. [3 body] Na obrazku mate 2 Čtverce, v každém 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, ktere se vam nepodarí s nicím spojit, strucne vysvetlete proc.
Poznamka: Zatímco v levem ctverci jsou konkretní jazyky, v pravem jsou vsechny jazyky odvozene od jazyka L, kterí není specifikovan. Do praveho ctverce proto zaznacte inkluze, ktere 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
• • •
CC
L41 L42 L43
• • •
L21
L22
L23
L51
L52
L53
L31
L32
L33
L61
L62
L63
Ln = (a, 6}*
L21 = (a} L31 = (a6, a66}
L12 = (a}.(6}+ L22 = (a}+ L32 = (6}+
L13 = co-(a,6}*
L23 = (a}*
L33 = (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
IB102 - úkol 2
Odevzdání: 4.10. 2010
Vypracoval(a): UCO: Skupina:
2. [3 body] Mejme jazyk L = [ab, ba, aba] nad abecedou S = [a, b}. Zjistěte, kolik slov nm nasledujúci jazyk:
co- ((co-L)2)
Odpoveď zduvodnete.