# 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: (Sc U Tc)c, where Sc is the complement of S.

The algorithm to calculate a finite state automaton which accepts the intersection of the languages accepted by two automatons A1 and A2 is thus the following:

1. Construct finite state automata B1 and B2 which accept the complement of the languages accepted by A1 and A2 (see the relevant algorithm).
2. Construct finite state automaton C which accepts the union of the languages accepted by B1 and B2 (see the relevant algorithm).
3. Remove useless and unreachable states from C, obtaining D (see the relevant algorithms to remove useless and unreachable states).
4. Minimise D to obtain E (see the relevant algorithm).
5. 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:

1. Start by constructing automata which recognise the complement of these automata:

2. Take the union of these resultant automata:

3. Remove useless and unreachable states:

4. Minimise automaton:

5. 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: