Determinisation

automata-theory

Definition

Determinisation

Nondeterministic finite automata can be transformd into deterministic finite automata using the method of determinisation.

For a given nondeterministic finite automaton :

find a deterministic finite automata :

such that and are equivalent, meaning that they accept the same language.

Proof

Example

First, reconstruct the possible next states for each state and input symbol:

1
2
3

Using the above table, we can already observe the start state and the accepting states:

Start state:

The start state is the same as the start state of the original automaton , which is .

Accepting states:

The accepting states are the states that contain any of the accepting states of the original automaton , which are those that contain the state .

Now, we can construct the deterministic finite automaton :

First, start with the start state :

By using and as input symbols on , new states are created:

Both states are not part of the table above, so they need to be added:

No new states are created, so the table and thus the automaton is complete:

The created deterministic finite automata is equivalent to the origin automaton , meaning that they accept the same language.