IB102 - úkol 6 - řešení
Odevzdání: 1.11.2010
Vypracoval: James Bond UCO: 007
Skupina: MI6
Bonušová 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 da rozsírit 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á. Napnklad {ab, ba} Y {b, c} = {abb, bab, bba, abc, acb, cab, bac, bca, cba}. Formálne 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).
Řešení: Idea resení spocíva v konstrukci „asynchronního" paralelního spojení dvou automatu. Na rozdál od klasickeho synchronnáho paralelního spojená se automaty nepohybujá zároveň, ale naopak kazdy zvlast'. Vzdy jeden „táhne" a druhá „stojá".
Necht' tedy A1 = (Q1, S,ó1,q1, F1) a A2 = (Q2, S,ó2,q2, F2). Novy automat bude A = (Q1 x Q2, S, ó, (q1,q2),F1 x F2), kde:
5((p1,p2),a) = Ó1 (P1,a) x {P2} U {p1} x Ó2(p2,a)
Dukaz korektnosti teto konstrukce ponechavame ctenari jako cvicená. (V zadaná jsme jej ani nepoňzadovali.)
Pro jednoduchost jsme uvazovali, ze oba puvodná automaty majá stejnou vstupná abecedu. Resená by se dalo zobecnit i na prípad, kdy automat A1 má vstupná abecedu S1 a automat A2 má vstupná abecedu S2. Vásledná automat by pak mel vstupná abecedu S1 U S2.
Poznámka: V anglicke literature se tato operace vetsinou nazáva „shuffle" a oznacuje se symbolem o. V zadaná tohoto prákladu jsme schválne zvolili jine znacená, abychom zabránili moznosti dohledat resená v literature, práp. na webu.