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 $\mathcal{A}$:

$$\mathcal{A}=(Q,\Sigma ,\delta ,q_0,F)\text{with}\delta \subseteq Q\times (\Sigma \cup \{\epsilon \})\times Q$$

find a deterministic finite automata $\hat{\mathcal{A}}$:

$$\hat{\mathcal{A}}=(\hat{Q},\Sigma ,\hat{\delta },\widehat{q_0},\hat{F})\text{with}\delta \subseteq \hat{Q}\times \Sigma \times \hat{Q}$$

such that $\mathcal{A}$ and $\hat{\mathcal{A}}$ are equivalent, meaning that they accept the same language.

Example

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

${\delta }^{\ast }$	$a$	$b$
1	$\{1,2,3\}$	$\{2,3\}$
2	$\varnothing$	$\{3\}$
3	$\{1,2,3\}$	$\{2\}$

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

Start state: $\{1\}$

The start state is the same as the start state of the original automaton $\mathcal{A}$, which is $1$.

Accepting states: $\{\{1\},\{1,2,3\}\}$

The accepting states are the states that contain any of the accepting states of the original automaton $\mathcal{A}$, which are those that contain the state $1$.

Now, we can construct the deterministic finite automaton $\hat{\mathcal{A}}$:

First, start with the start state $\widehat{q_0}=\{1\}$:

${\hat{\delta }}^{\ast }$	$a$	$b$
$\{1\}$	$\{1,2,3\}$	$\{2,3\}$

By using $a$ and $b$ as input symbols on $\widehat{q_0}=\{1\}$, new states are created:

$$\{1,2,3\},\{2,3\}$$

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

${\hat{\delta }}^{\ast }$	$a$	$b$
$\{1\}$	$\{1,2,3\}$	$\{2,3\}$
$\{1,2,3\}$	$\{1,2,3\}$	$\{2,3\}$
$\{2,3\}$	$\{1,2,3\}$	$\{2,3\}$

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

The created deterministic finite automata $\hat{\mathcal{A}}$ is equvalent to the origin automaton $\mathcal{A}$, meaning that they accept the same language.