Union of Finite State Automata

Algorithm

Given two FSA M1 and M2, we want a FSA M which recognises a string exactly when either M1 or M2 (or both) recognise it.

  1. construct regular grammars G1 and G2 from FSA M1 and M2 (see relevant algorithm)
  2. apply the union of regular grammars to G1 and G2 to construct G (see relevant algorithm)
  3. construct and FSA M from G (see relevant algorithm)

Example

Refer to the examples in the sections referred to above for examples of the individual steps.

Exercises

Construct a FSA which recognises the union of the languages generated by the following FSA: