Midterm Lesson 2: NFA in Automata Theory

Non-Deterministic Finite Automata (NFA)

• NFA is easier to construct than DFA for a given regular language.
• In NFA, there exist many paths for specific input from the current state to the next state.
• Not every NFA is a DFA, but each NFA can be translated into a DFA.

Definition of NFA

• Defined similarly to DFA, but with two exceptions:
  • Contains multiple next states
  • Contains ε transition
• NFA has five components: Q (finite set of states), ∑ (finite set of input symbols), q0 (initial state), F (final state), and δ (transition function)
• δ: Q x ∑ → 2Q

Graphical Representation of NFA

• Represented by digraphs called state diagrams
• States are represented by vertices
• Arcs labeled with input characters show transitions
• Initial state is marked with an arrow
• Final state is denoted by a double circle

Examples of NFA

• Example 1: Draw the transition diagram and table of the FA with Q = {q0, q1, q2}, ∑ = {0, 1}, q0 = {q0}, and F = {q2}
• Example 2: Draw the NFA with ∑ = {0, 1} that accepts all strings with 01
• Example 3: Draw the NFA with ∑ = {0, 1} that accepts all strings of length at least 2