9. The subset construction

Subset Construction

The Subset Construction is an algorithm that carries out a conversion from a nondeterministic automaton to its deterministic equivalent.

Equivalence of DFAs and NFAs

Given two automata $A$ and $A^{\prime }$ that accept the same language are said to be equivalent. For every NFA $A$, there is a DFA $A^{\prime }$ equivalent to $A$.

Converting NFA to DFA

Given an NFA as follows, turn it into an equivalent DFA.

digraph {
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; s;
	node[shape=circle];
	init->s
	
	s->r [label=b]
	s->q [label=ε]
	q->s [label=a]
	r->q [label=a]
	r->q [label=b]
	r->r [label=a]
}

In a DFA, we are not allowed multiple choices, being stuck or to use $ϵ$-jumps. We need to define:

• new states: named after subsets of the original NFA’s states
• new initial state: the set containing the original NFA’s initial state, plus all states that are reachable from it by some $ϵ$-jumps
• new favourable states: those subsets that contain at least one of the original NFA’s favourable states

digraph {
	init[shape=point]
	node[shape=doublecircle]; s, sq, sr, sqr;
	node[shape=circle];
	init->sq
	
	s   [label="{s}"]
	sq  [label="{s,q}"]
	sr  [label="{s,r}"]
	sqr [label="{s,q,r}"]
	
	0  [label="{}"]
	r  [label="{r}"]
	q  [label="{q}"]
	qr [label="{q,r}"]
}

The new states are named after subsets of the old states:

digraph {
	label="for each symbol x in the input alphabet"
	rankdir=LR
	P->a
	a[label="?"]
}

Where $?$ is the set of all those states that are reachable from some state in the set $P$, either by a $x$-arrow or by an $x$-arrow followed by possibly one or more $ϵ$-jumps (but not $ϵ$-jump then $x$-arrow).

In a DFA every state must have one $a$-arrow out and one $b$-arrow out. We being with the initial state an compute where two arrows go from it:

	$a$	$b$
$\{s,q\}$	$\{s,q\}$	$\{r\}$

We look at the NFA again to find that:

• from $s$ we cannot reach anything by an $a$-arrow
• from $q$ we can reach $\boxed{s}$ by an $a$-arrow
• from $q$ we can reach $\boxed{q}$ by an $a$-arrow followed by an $ϵ$-jump

Hence the $a$-arrow from state $\{s,q\}$ goes to state $\{s,q\}$ itself.

• from $s$ we can reach $\boxed{r}$ by a $b$-arrow
• from $q$ we cannot reach anything by a $b$-arrow

The $b$-arrow from state $\{s,q\}$ goes to state $\{r\}$.

Next, for every obtained new state, we compute where the $a$-arrow and the $b$-arrow goes from it. We do this until there are no newly obtained states.

	$a$	$b$
$\{s,q\}$	$\{s,q\}$	$\{r\}$
$\{r\}$	$\{q,r\}$	$\{q\}$
$\{q,r\}$	$\{s,q,r\}$	$\{q\}$
$\{q\}$	$\{s,q\}$	$\varnothing$
$\{s,q,r\}$	$\{s,q,r\}$	$\{q,r\}$
$\varnothing$	$\varnothing$	$\varnothing$

Final DFA

digraph {
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; sq, sqr;
	node[shape=circle];
	init->sq
	
	sq  [label="{s,q}"]
	sqr [label="{s,q,r}"]
	
	0  [label="{}"]
	r  [label="{r}"]
	q  [label="{q}"]
	qr [label="{q,r}"]
	
	sq->sq   [label=a]
	sq->r    [label=b]
	r->qr    [label=a]
	r->q     [label=b]
	qr->sqr  [label=a]
	qr->q    [label=b]
	q->sq    [label=a]
    q->0     [label=b]
	sqr->sqr [label=a]
	sqr->qr  [label=b]
	0->0     [label=a]
	0->0     [label=b]
}