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

Nondeterminism: Multiple Transitions and Choices

Understand how NFAs can have multiple transitions for the same input symbol and what it means for computation to branch.

Nondeterminism: Multiple Transitions and Choices

You'll learn: How NFAs allow multiple transitions from the same state on the same input symbol, enabling computational branching.

The Core Difference from DFAs

In a DFA (Deterministic Finite Automaton), computation follows one clear path: for each state and input symbol, there's exactly one next state. NFAs (Nondeterministic Finite Automata) break this rule — from a given state, reading the same input symbol can lead to multiple possible next states.

What Multiple Transitions Mean

Imagine standing at a fork in a road where both paths are labeled "a". In a DFA, you'd be stuck — ambiguity isn't allowed. In an NFA, you can explore both paths simultaneously. The computation "branches" into multiple parallel possibilities.

For example, an NFA might have:

  • State q₁ reading symbol a → transitions to q₂
  • State q₁ reading symbol a → also transitions to q₃

Both transitions exist at the same time. The machine doesn't "choose" one — it conceptually explores all possibilities.

Acceptance Through Any Path

An NFA accepts a string if at least one computational path leads to an accept state. Think of it like solving a maze with the power to clone yourself: if any clone reaches the exit, you win. It doesn't matter if other paths fail.

This nondeterministic choice doesn't make NFAs physically "magic" — it's a mathematical abstraction that simplifies designing automata for complex patterns. Later, you can always convert an NFA to an equivalent DFA that produces the same language.

Key Takeaway: NFAs allow multiple transitions for the same input symbol, creating branching computation where acceptance requires only one successful path among many possibilities.