1

I want some examples of how to take intersection of two finite autometa machines(with diagram).

I have learned taking union of two finite autometas.

I have searched throughout the internet but hasn't find anything.

Umair Ayub
  • 19,358
  • 14
  • 72
  • 146
  • Union of two Finite automate is simple, you just need to add a new starting stat then add ^-transition to both finite automate then convert NFA to DFA. ...for intersection you need to create completely new Finite automate in which there is a stat for each possible pair of states in input Finite automata. – Grijesh Chauhan Jul 18 '13 at 16:27
  • [read](http://math.stackexchange.com/questions/147457/intersection-of-two-deterministic-finite-automata) – Grijesh Chauhan Jul 18 '13 at 16:47

1 Answers1

4

The idea is pretty straightforward, although I can see where the confusion comes in. I will give a text/symbolic description of the process for making the intersection (union, difference) machines via the Cartesian Product Machine construction (same thing as you are talking about).

A DFA is a 5-tuple (E, Q, q0, A, f) where

E is the input alphabet, a non-empty finite set of symbols
Q is the set of states, non-empty and finite
q0 is the start state, an element of Q
A is the set of accepting or final states, a subset of Q
f is the transition function, taking pairs from Q x E to Q

Say we have two machines M' = (E', Q', q0', A', f') and M'' = (E'', Q'', q0'', A'', f''). To make the discussion easier, we assume E' = E''. We will now construct M''' so that 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) where x in A' and y in A'' (for union, x in A' or y in A''; for difference, x in A' but not y in A'').
Take f'''((x, y), e) = (f'(x, e), f''(y, e)).

There you go! Let's now consider two machines: one which accepts a^2n, and one which accepts a^3n (the intersection should be a machine accepting a^6n... right?).

For M', we have...

E' = {a}
Q' = {s0, s1}
q0' = s0
A' = {s0}
f'(s0, a) = s1, f'(s1, a) = s0

For M'', we 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''', we get...

E''' = {a}
Q''' = {(s0, t0), (s0, t1), (s0, t2), (s1, t0), (s1, t1), (s1, t2)}
q0''' = (s0, t0)
A''' = {(s0, t0)} for intersection, {(s0, t0), (s0, t1), (s0, t2), (s1, t0)} for union, {(s0, t1), (s0, t2)} for 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 you go! Please let me know if this needs clarification.

Source: How to use the intersection construction to form a DFA?

Salem
  • 17
  • 7
ashishkr
  • 51
  • 3