Non-Deterministic Finite Automaton (NFA)

It might seem at a surface level that NFAs seem more powerful than DFAs, but they are not.

Non-Deterministic Finite Autonomaton

This is pretty much the same as the DFA, except for $\delta$. A deterministic finite automaton (DFA) is a five-tuple $⟨h,\Sigma ,Q,q_0,A,{\delta }_i⟩$ where:

• $\sum$ is a finite set of symbols (the alphabet).
• $Q$ is a finite set of states.
• $q_0\in Q$ is the start state.
• $A\subseteq Q$ is the set of accepting states.
• $\delta :Q\times \sum \to 2^{\mathbf{Q}}$ is the transition function that, given a state $q$ and alphabet symbol $a$, returns the new state $q^{\prime }$ to transition to after processing the symbol $a$ in state $q$ ($2^Q$ is the set of all subsets of $Q$)

$ϵ$-transitions

To make it easier to more systematically combine NFAs, we add $ϵ$-transitions. Whenever the NFA is in a state with an outgoing $ϵ$-transition, it may optionally choose to follow that transition without processing any symbols from the input word.

Using $ϵ$-transitions, we can combine the two DFAs without having to modify them, just by adding a new start state with $ϵ$-transitions to the former start states of the two DFAs, as shown in the following diagram:

From the new start state, a path through the NFA starts by following one of the $ϵ$-transitions to one of the former start states, depending on whether the input word is a decimal or hexadecimal number.

So the $ϵ$ transition is optional. The example below illustrates this: