How to take intersection of two Finite Autometas -
i want examples of how take intersection of 2 finite autometa machines(with diagram).
i have learned taking union of 2 finite autometas.
i have searched throughout internet hasn't find anything.
please don't vote down me.
the idea pretty straightforward, although can see confusion comes in. give text/symbolic description of process making intersection (union, difference) machines via cartesian product machine construction (same thing talking about).
a dfa 5-tuple (e, q, q0, a, f) where
e input alphabet, non-empty finite set of symbols q set of states, non-empty , finite q0 start state, element of q set of accepting or final states, subset of q f transition function, taking pairs q x e q
say have 2 machines m' = (e', q', q0', a', f') , m'' = (e'', q'', q0'', a'', f''). make discussion easier, assume e' = e''. construct m''' l(m''') = l(m') intersect (or union or difference) l(m'').
take e''' = e'' = e' take q''' = q' x q'' take q0''' = (q0', q0'') take a''' = (x, y) x in a' , y in a'' (for union, x in a' or y in a''; difference, x in a' not y in a''). take f'''((x, y), e) = (f'(x, e), f''(y, e)).
there go! let's consider 2 machines: 1 accepts a^2n, , 1 accepts a^3n (the intersection should machine accepting a^6n... right?).
for m', have...
e' = {a} q' = {s0, s1} q0' = s0 a' = {s0} f'(s0, a) = s1, f'(s1, a) = s0
for m'', have...
e'' = {a} q'' = {t0, t1, t2} q0'' = t0 a'' = {t0} f''(t0, a) = t1, f''(t1, a) = t2, f''(t2, a) = t0
for m''', get...
e''' = {a} q''' = {(s0, t0), (s0, t1), (s0, t2), (s1, t0), (s1, t1), (s1, t2)} q0''' = (s0, t0) a''' = {(s0, t0)} intersection, {(s0, t0), (s0, t1), (s0, t2), (s1, t0)} union, {(s0, t1), (s0, t2)} difference. f'''((s0, t0), a) = (s1, t1), f'''((s1, t1), a) = (s0, t2), f'''((s0, t2), a) = (s1, t0), f'''((s1, t0), a) = (s0, t1), f'''((s0, t1), a) = (s1, t2), f'''((s1, t2), a) = (s0, t0).
and there go! please let me know if needs clarification.
Comments
Post a Comment