# Intersection of Finite State Automata

## Algorithm

Intersection can be defined in terms of complementation and
union. Since we have algorithms to obtain the union and
complement of a finite state automaton, we can give a construction
to calculate their intersection.

Recall that the intersection of two sets *S* and
*T* is equal to: (*S*^{c} U *T*^{c})^{c},
where *S*^{c} is the complement of *S*.

The algorithm to calculate a finite state automaton which
accepts the intersection of the languages accepted by two
automatons *A*_{1} and *A*_{2}
is thus the following:

- Construct finite state automata
*B*_{1} and
*B*_{2} which accept the complement of the
languages accepted by *A*_{1} and
*A*_{2} (see the relevant
algorithm).
- Construct finite state automaton
*C* which accepts the union
of the languages accepted by *B*_{1} and
*B*_{2} (see the relevant
algorithm).
- Remove useless and unreachable states from
*C*, obtaining *D*
(see the
relevant algorithms to remove useless
and unreachable states).
- Minimise
*D* to obtain *E* (see the relevant
algorithm).
- Calculate the inverse of
*E*.

Note that steps 3 and 4 are not necessary, but are done to simplify
step 5 (recall that to calculate the complement of a finite
state automaton, the original automaton has to be made deterministic,
which can be a very messy and error-prone process with large automata).

## Example

Consider the following two FSA:

- Start by constructing automata which recognise the complement of these
automata:

- Take the union of these resultant automata:

- Remove useless and unreachable states:

- Minimise automaton:

- Construct an automaton accepting the complement of the language recognised by the
minimised automaton:

## Exercises

Calculate an automaton which recognises the intersection of the languages recognised
by the following two automata: