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: A non-deterministic finite automaton (NFA) $M$ consists of the following

a set of states $Q$ and transitions $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: A computation path of 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$ accepts a 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$.