3. NFAs

Jan 18, 2022

Nondeterministic Finite Automata

• same symbol may have multiple transitions (or none) from a state
• special transition with $ϵ$
• if input cannot be consumed automaton halts
• explore all paths: if any choice consumes all input symbols and ends in accept state, then the input is accepted

• reject input if there is no computation of the NFA that accepts the string, i.e. when for all possible computation paths:

  • all the input is consumed and the automaton is in a non-accepting state, or
  • the input cannot be consumed

• NFAs can express languages easier than DFAs (fewer states and transitions)

Formal definition

• $M=(Q,\mathrm{\Sigma },\delta ,q_0,F)$ where
  • $Q$ is set of states
  • $\mathrm{\Sigma }$ is input alphabet and $ϵ\notin \mathrm{\Sigma }$
  • $\delta$ is transition function (non-deterministic)
  • $q_0$ is initial state
  • $F$ is set of accepting states (0 or more)

Transition function

• $\delta (q,x)=\{q_1,q_2,...,q_k\}$   (can be $\mathrm{\varnothing }$)
• resulting states reached by following one transition with input symbol $x$

Extended transition function

• extended transition function: $\delta (q,w)=\{q^{\prime },...\}$ applied on string $w$
• special case: for any state $q$   =>   $q\in {\delta }^{\ast }(q,ϵ)$
• in general: $q_j\in {\delta }^{\ast }(qi,w)$ there is a path from $q_j$ to $q_i$ and transition labels $w$

Language accepted by NFA

• The language accepted by M is $L(M)=\{w_1,w_2...,w_n\}$ where for each $w_m$ ${\delta }^{\ast }(q_0,w_m)=\{q_i,...,q_k,...,q_j\}$ and there is some $q_k\in F$ (accepting state)
• NFA accepts the regular languages
• equivalence of machines: machine $M_1$ is equivalent to $M_2$ if $L(M_1)=L(M_2)$
• NFAs and DFAs have the same the same computation power i.e. they accept the same set of languages
• Proof steps: show that Languages accepted by NFAs $\iff$ Regular languages
  • Languages accepted by NFAs $\supseteq$ Regular languages
    • every DFA is trivially a NFA
    • any language L accepted by a DFA is also accepted by NFA
  • Languages accepted by NFAs $\subseteq$ Regular languages
    • any NFA can be converted to an equivalent DFA
    • any language L accepted by NFA is also accepted by DFA

Converting NFA to DFA

• input: an NFA M
• output: an equivalent DFA M' with $L(M)=L(M^{\prime })$
• NFA has states $q_0,q_1,q_2,...$
• DFA has states from the power set $\mathrm{\varnothing },\{q_0\},\{q_1\},\{q_0,q_1\},\{q_1,q_2,q_3\},...$

Steps

1. initial state of NFA: $q_0$ and ${\delta }^{\ast }(q,ϵ)=\{q_0,...\}$ initial state of DFA: $\{q_0\}$

2. for every DFA's state $\{q_i,q_j,...,q_m\}$, compute in NFA (union):

   $$\{q_i^{\prime },q_j^{\prime },...,q_n^{\prime }\}=\{\begin{array}{l}{\delta }^{\ast }(q_i,a)\\ \cup {\delta }^{\ast }(q_j,a)\\ ...\\ \cup {\delta }^{\ast }(q_m,a)\end{array}$$

   and add transitions to DFA: $\delta (\{q_i,q_j,...,q_{,}\},a)=\{q_i^{\prime },q_j^{\prime },...,q_n^{\prime }\}$

3. Repeat step 2 for every state in DFA and symbols in alphabet until no more states can be added to the DFA

4. For every DFA's state $\{q_i,q_j,...,q_m\}$, if some $q_j$ is accepting state in NFA, then $\{q_i,q_j,...,q_m\}$ is accepting state in DFA