Course contentsShow
← Computer Science
Lesson 1793 of 2,87240. Theory of Computation: Regular LanguagesFree lesson

NFA Definition and Components

Define nondeterministic finite automata, their five-tuple notation, and how they differ from DFAs in transition functions.

NFA Definition and Components

What you'll learn: You'll discover what nondeterministic finite automata are, their formal structure, and how they differ from the deterministic automata you've already studied.

What is an NFA?

A Nondeterministic Finite Automaton (NFA) is a computational model similar to a DFA, but with a crucial superpower: it can have multiple possible next states for a given input symbol, or even transition without consuming any input at all.

Think of it like choosing your path in a maze. A DFA is like following strict signs—each sign gives you exactly one direction. An NFA is like having a magic ability to explore multiple paths simultaneously or teleport ahead without following the path.

The Five-Tuple Notation

Like DFAs, NFAs are formally defined as a five-tuple:

NFA = (Q, Σ, δ, q₀, F)

  • Q: Finite set of states
  • Σ: Input alphabet
  • δ: Transition function (this is where NFAs differ!)
  • q₀: Start state (in Q)
  • F: Set of accepting states (subset of Q)

The Key Difference: Transition Functions

Here's what makes NFAs nondeterministic:

DFA transition function: δ: Q × Σ → Q
Maps a state and symbol to exactly one next state.

NFA transition function: δ: Q × (Σ ∪ {ε}) → P(Q)
Maps a state and symbol (or ε, the empty string) to a set of possible states (the power set of Q).

This means an NFA can:

  1. Have zero, one, or many transitions for the same state-symbol pair
  2. Make ε-transitions (move without reading input)
  3. "Guess" which path to take

Key Takeaway: NFAs extend DFAs by allowing nondeterministic transitions—multiple next states or empty-string transitions—making them more flexible for expressing patterns, though ultimately equivalent in computational power.