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.
- Create a state for every element in P(Q) (the power set of
the set of states)
- Set { S } as the initial state (where S was the initial
state in the original automaton).
- 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.
- 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) }
- Remove useless and unreachable states from M'
Example
Consider the following FSA:
- Create a state for every element of the power set of states of
the original automaton:
- Set { S } to be the initial state of the new automaton:
- 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.
- 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.
- Remove unreachable states:
- Remove useless states:
Exercises
Make the following automata deterministic:
-
-