Nondeterministic finite automaton

A nondeterministic finite automaton assigns a set of possible successor states to each state-symbol pair and accepts when at least one run ends in a final state.

An epsilon-NFA is a nondeterministic finite automaton that may traverse transitions labelled $ϵ$ without consuming an input symbol.

The epsilon closure of a state set $S$ consists of every state reachable from $S$ using zero or more epsilon transitions.

The subset construction converts an epsilon-NFA into a deterministic finite automaton. Its states are subsets of NFA states, its initial state is the epsilon closure of the NFA initial state, and every symbol transition is followed by another epsilon closure.

Without epsilon transitions, defineA word is accepted when the set reached from the initial state meets the final set.

For $w=a_0\cdots a_{n-1}$, a witnessing sequence from $p_0$ to $p_n$ satisfies $p_{i+1}\in \Delta (p_i,a_i)$. Induction on word length shows that $q^{\prime }\in \hat{\Delta }(q,w)$ exactly when such a sequence runs from $q$ to $q^{\prime }$.

The powerset construction turns an NFA with state set $Q$ into a DFA with state set $\mathcal{P}(Q)$, transitionand accepting subsets that meet the NFA final set.

In the convention used here, a Brzozowski NFA has one final state, every state can reach it, and each word labels a path to it from exactly one starting state.

For distinct accessible subset states, choose a state in their symmetric difference. A word taking it to the unique final state accepts from one subset; uniqueness of the starting state prevents acceptance from the other. Thus the accessible part of the subset automaton is irreducible.