IB102 - úkol 6
Odevzdání: 1.11.2010
Vypracoval(a): UCO: Skupina:
Bonusový příklad [3 body] Mejme binární operaci Y, kterou lze intuitivně popsat tak, ze u Y v je množina vsech slov, ktera vzniknou tak, Ze se symboly z u promíchají se symboly z v s tím, ze se poradí symbolu z u a symbolu z v zachová. Napríklad aba Y cd = {abacd,abcad,acbad,cabad,abcda,acbda,cabda,acdba,cadba,cdaba}. Formálne se tato operace na slovech dá definovat takto:
U Y V = {U1V1U2V2 • • • Uk Vk | k E N,U = U1U2 • • • Uk ,V = V1V2 • • • Vk, Vi : Ui ,Vi E S*}
Tato operace se dá rozsínt i na jazyky, intuitivne je L1 Y L2 jazyk, která vznikne tak, ze se operace Y aplikuje postupne na vsechny dvojice slov z jazyku L1 a L2 a vásledne mnoziny se sjednotá. Napráklad {ab, ba} Y {b, c} = {abb, bab, bba, abc, acb, cab, bac, bca, cba}. Formalne definujeme:
L1 Y L2 = U {u Y v | u E L1, v E L2}
Mejme dva nedeterministicke konecne automaty A1, A2. Popiste konstrukci automatu A takoveho, ze L (A) = L(A1) Y L(A2).