Skip to main content

3. Nondeterministic Finite Automata

09/02/23

What is NFA​

  • NFA have transition functions that map a given state and an input symbol to zero or more successor states.
  • They have more than one initial state. Machine has a choice As long as the word is valid from one initial state, then its valid in the language

A nondeterministic finite automaton (DFA) A=(Q,Σ,δ,S,F)A = (Q,\Sigma,δ,S,F)

  1. A finite set of states QQ
  2. A finite set of input symbols, the alphabet, Σ\Sigma
  3. A transition function δ∈Q×Σ→P(Q)δ\in Q \times \Sigma \to P(Q)
  4. An initial state S⊆QS \subseteq Q
  5. A set of final (or accepting) states F⊆QF\subseteq Q

In contract to a DFA, NFA may have many initial states, not just one, and its transition function maps a state and an input symbol to a set of possible successor states, not a single state.

The language accepted by an NFA​

  • To define the extended transition function for NFAs we use a generalisation of the union operation ∪\cup.
  • All the states anded together