Non-Deterministic Finite Automaton

A non-deterministic finite (state) automaton (NFA) is an extension of its deterministic version, allowing it to choose between multiple paths. It does this using the epsilon transitions. In a sense, an NFA is more powerful version of a DFA because the epsilon transitions allows it to run paths in parallel.

Definition §

Non-deterministic Finite Automata (NFA) ^definition-dfa

An NFA $M$ is defined to contain

• An input alphabet, $\Sigma$
• A set of states, $Q=\{q_1,q_2,\dots \}$
• An initial state, $q_0\in Q$
• A state transition function, $\delta$ which takes the current state and the next character of the input string, and instead of returning a state, returns a set of possible states.:$\delta :Q\times \Sigma \to \mathcal{P}(Q)\delta (q_{cur},a)=\{q_{nex{t}_1},q_{nex{t}_2},\dots \}$
  • $\mathcal{P}(Q)$ is the power set of $Q$, and is the set of all possible subsets of $Q$.
• A set of accept states, $F\subseteq Q$

NFAs are essentially the same as DFA, except for the transition function.

Epsilon Closure ^definition-epsilon-closure

Let $N=(Q,\Sigma ,\delta ,q_0,F)$ be an NFA. Let $R\subseteq Q$, be any subset of states of $Q$. Then the epsilon-closure (or $ϵ$-closure) of a state $r$ is given by:

$$E(r)=\{q\in Q|\exists \text{ a computation path ending at q from r consisting only of k ϵ-transitions},k\in \mathbb{N}\}$$

In other words, if we start at the state $r$, and follow a computation path from $r$ to some other state $q$ by only taking epsilon transitions, then we add $q$ to $E(r)$.

The epsilon closure of a set is then the union of the $ϵ$-closures of its elements:

$$E(R)=\bigcup _{r\in R}E(r)$$

Note the similarity between epsilon-closure and transitive closure of a graph.

Epsilon Transitions §

NFAs introduce a new type of transition known as epsilon transitions or $ϵ$-transitions. These transitions do not consume input characters from the input string.

For example, take the NFA below:

%%🖋 Edit in Excalidraw, and the dark exported image%%

This NFA has two epsilon transitions (in bold), which means when given an input string, it can ‘jump’ from A, going to B or C if possible. It could also not take the transitions, staying in A.

Epsilon-transitions have some key properties:

• Any DFA containing an $ϵ$-transition becomes an NFA.
• Any state connected to an initial state via an epsilon transition becomes an initial state

Theorems §

T1: Theorem of Equivalence ^t1

Every NFA has an equivalent DFA. Let $N$ be an NFA. Then, there exists a DFA $D$, such that:

$$N\sim D$$

$N$ and $D$ are equivalent. #TODO proof

Examples §

1: NFA to equivalent DFA

Convert the NFA given below to an equivalent DFA: %%🖋 Edit in Excalidraw, and the dark exported image%%

The main procedure is to look at all sets of states that we can transition to for a given input:

• First, we look at all the initial states. Recall that any state connected to an initial state by an epsilon-transition also becomes an initial state. So we have $q_0=\{1,3\}$ (as 3 is connected to 1 via $ϵ$-transition). Let’s call it $A$.
• From $A=\{1,3\}$:
  • If we encounter a $b$, we can’t do anything (since there is no transition in 1 or 3 that require a $b$. This is notated as the empty set, $\varnothing$.
  • If we decide to take the
  • If we encounter an $a$, however, we can go to the set of states $\{1,3\}{\to }_a\{1,2,3\}$. Let’s call this new set $B$
• From $B=\{1,2,3\}$:
  • If we encounter an $a$:
    • If we take the

#todo