Skip to content

3. NFAs

Jan 18, 2022

Nondeterministic Finite Automata

  • same symbol may have multiple transitions (or none) from a state
  • special transition with \(\epsilon\)
  • 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, \Sigma, \delta, q_0, F)\) where
    • \(Q\) is set of states
    • \(\Sigma\) is input alphabet and \(\epsilon \notin \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 \(\emptyset\))
  • resulting states reached by following one transition with input symbol \(x\)

Extended transition function

  • extended transition function: \(\delta(q, w) = \{ q', ... \}\) applied on string \(w\)
  • special case: for any state \(q\)   =>   \(q \in \delta^*(q, \epsilon)\)
  • in general: \(q_j \in \delta^*(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^*(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 \(\Leftrightarrow\) 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')\)
  • NFA has states \(q_0, q_1, q_2, ...\)
  • DFA has states from the power set \(\emptyset, \{q_0\}, \{q_1\}, \{q_0, q_1\}, \{q_1, q_2, q_3\},...\)

Steps

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

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

    \[\begin{equation} \{q_i', q_j', ..., q_n'\} = \begin{cases} \delta^*(q_i, a) \\ \cup \delta^*(q_j, a) \\ ... \\ \cup \delta^*(q_m, a) \end{cases} \end{equation}\]

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

  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