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

Popular posts from this blog

php - Calling a template part from a post -

Firefox SVG shape not printing when it has stroke -

How to mention the localhost in android -