# Lecture 6: Non-Deterministic Finite Automata

## Example

The following figure shows the *state diagram* of a non-deterministic finite automaton (NFA),

The automaton accepts the set of all strings that contain \(11\) or \(101\) as a substring.

## Non-deterministic Finite Automata

Definition:Anon-deterministic finite automaton(NFA) \(M\) consists of the following

- a set of
states\(Q\) andtransitions\(T\subseteq Q \times Q \times (\Sigma\cup \{\varepsilon\})\) between states labeled by alphabet symbols or the empty string \(\varepsilon\),- a start state \(q_0\in Q\),
- a set of accept states \(F\subseteq Q\).

## Language of Non-deterministic Finite Automata

Definition:Acomputation pathof an NFA \(M\) for a string \(w\in \Sigma^\ast\) is a sequence of transitions \((r_0,r_1,x_1),(r_1,r_2,x_2),\ldots,(r_{m-1},r_m,x_m)\in T\) such that \(r_0=q_0\) is the start state and \(w=x_1\cdots x_m\). An NFA \(M\)acceptsa string \(w\) if there exists a computation path for \(w\) that ends in an accept state, so that \(r_m\in F\).

The *language* of an NFA is the set of strings that \(M\) accepts, \[
L(M) = \{ w\in \Sigma^\ast \mid \text{there exits an accepting computation path in $M$ for $w$} \}.
\]

## Closure Properties of Regular Languages

Theorem:The set of regular languages is closed under union, concatenation, and Kleene star operations.

**Lemma:** Let \(M_1\) and \(M_2\) be NFAs, then there exists an NFA \(M\) with \[
L(M)=L(M_1)\cup L(M_2).
\] *Proof sketch:* Create a designated start state with \(\varepsilon\)-transitions to the start state of \(M_1\) and the start state of \(M_2\). An accepting computation path in \(M\) corresponds to either an accepting computation path in \(M_1\) or an accepting computation path in \(M_2\). \(\square\).

**Lemma:** Let \(M_1\) and \(M_2\) be NFAs, then there exists an NFA \(M\) with \[
L(M)=L(M_1) L(M_2).
\] *Proof sketch:* Add \(\varepsilon\)-transitions from the accept states of \(M_1\) to the start state of \(M_2\). An accepting computation path in \(M\) corresponds to an accepting computation paths in \(M_1\) followed by an accepting computation path in \(M_2\). \(\square\).

**Lemma:** Let \(M_0\) be an NFA, then there exists an NFA \(M\) with \[
L(M)=L(M_0)^\ast.
\] *Proof sketch:* Create a designated start state with a \(\varepsilon\)-transition to the start state of \(M_0\). Add \(\varepsilon\)-transitions from the accept states of \(M_0\) to this designated start state. Make this designated start state the unique accept state of \(M\). An accepting computation path in \(M\) corresponds to a finite sequence of accepting computation paths in \(M_0\). \(\square\).