# Nondeterministic finite automata (NFAs)

## Introduction

What makes DFA "deterministic" is that for any given state there is one and only one transition for any given letter of the alphabet. What if we want a machine that is able to "guess" between possible transitions for a single letter, or that might not have transition for some state and some letter? This is captured by nondeterministic finite automata (NFAs).

**Example.** Consider the following diagram:
Let us see how it would process the word $w = aabab$ using the following schema:
This schema shows that there are *two* distinct paths to process the word $w$. In fact, these paths are drastically different from each other: the path $(1,1,1,1,1,1)$ ends in the refuting state $1$, while the path $(1,1,1,1,2,3)$ ends in the accepting (!) state $3$.

How should we formally define an NFA so as to capture the above diagram? And how then should the language of an NFA be defined?

## Definition

Non-determinism in our setting has to allow for the following two cases:

1. Non-unique transitions ("guessing") for a fixed symbol

2. Partially defined transitions (i.e., some symbols might not be read)

Thus, we want have to generalize our transition function to output not just one state but a *set* of states (possibly empty).

:::info
**Definition (NFA).** A *non-deterministic finite automaton (NFA)* $\mathcal A = (Q,\Sigma, \delta, q_0, F)$ consists of:
1. a finite set of *states* $Q$
2. a finite set of *input symbols* or *labels* $\Sigma$
3. a *transition function* $\delta \colon Q \times \Sigma \to \mathcal P(Q)$[^1]
5. an *initial* or *start state* $q_0 \in Q$
6. a set of *final* or *accepting states* $F \subseteq Q$

Here $\mathcal P(Q) = \{ S \; | \; S \subseteq Q \}$ is the [power set](https://en.wikipedia.org/wiki/Power_set) of $Q$.
:::

## The language of an NFA

We have seen that NFAs can process the same words in essentially different paths: it's possible that one path accepts the word while the other rejects it. When defining the language of an NFA we will require that *at least one* computation results in an accepting state. This is expressed, again, through the extended transition function whose definition gets adjusted to the non-deterministic case. This time, the target set is the power set of $Q$:


:::info
**Construction ($\widehat{\delta}$ for NFAs).** We define $\widehat{\delta} \colon Q \times \Sigma^* \to \mathcal P(Q)$ inductively. Let $q \in Q$. For a word $w \in \Sigma^*$ we want to define $\widehat{\delta}(q,w)$ via case distinction:
1. $w = \varepsilon$: $\widehat{\delta}(q,\varepsilon) := \{q\}$
2. $w = xa$ for $x \in \Sigma^*$, $a \in \Sigma$: $\widehat{\delta}(q,xa) := \bigcup_{p \in \widehat{\delta}(q,x)} \delta(p,a)$.

An alternative but equivalent way to write this as follows: Let us write $\widehat{\delta}(q,x) = \{p_1, \ldots, p_k\}$ for some $k \in \mathbb N$. Then $\widehat{\delta}(q,xa) = \bigcup_{i=1}^k \delta(p_i,a)$.
:::

We then define the **accepted language** of an NFA $\mathcal A = (Q,\Sigma,\delta,q_0,F)$ to be the set of all words such that the **set**(!) $\widehat{\delta}(q_0,w)$ contains at least one accepting state. Formally:
$\mathcal L(A) := \{ w \in \Sigma^* \; | \; \widehat{\delta}(q_0,w) \cap F \neq \emptyset\}$

[^1]: Alternatively, as some sources in the literature do, transitions in an NFA could be modeled by *relations* $\Delta \subseteq Q \times \Sigma \times Q$. This doesn't change anything in an essential manner (i.e., the resulting notions of NFAs can be regarded as equivalent), but the respective constructions and concepts have to be defined in slighlty different ways. This is something to look out for when researching the literature.