Transforming a Non-Deterministic Finite State Automata Into a Deterministic One

Algorithm

Given an automaton M, with set of states Q, initial state S, transformations t and final states F, we will produce an equivalent automaton M' which is deterministic.

  1. Create a state for every element in P(Q) (the power set of the set of states)
  2. Set { S } as the initial state (where S was the initial state in the original automaton).
  3. Any state labelled with a set which includes at least one final state in the original automaton (an element of F) is set to be final.
  4. The new transition function will, when given a subset K of Q (a state of M'), and an input a, return the following state of M':

    { A' | there exists A:K such that A' is in t(B,a) }

  5. Remove useless and unreachable states from M'

Example

Consider the following FSA:

  1. Create a state for every element of the power set of states of the original automaton:

  2. Set { S } to be the initial state of the new automaton:

  3. Every state of the new automaton whose name denotes a set which includes a final state in the original automaton is set to be final. Originally, only B was a final state. Therefore all sets of states including B will be set to be final in the new automaton.

  4. Calculate the transitions. For example, where would the b transition lead to from the state { S, B }? In the original automaton, starting from S with input b took us to state B, while starting from B with input b took us non-deterministically either to state A or B.

  5. Remove unreachable states:

  6. Remove useless states:

Exercises

Make the following automata deterministic: