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

Epsilon Transitions

Learn about ε-transitions that allow state changes without consuming input symbols and their role in NFA flexibility.

Epsilon Transitions

What You'll Learn

You'll discover how ε-transitions (epsilon transitions) let an NFA change states "for free," without reading any input symbol, adding powerful flexibility to nondeterministic automata.

The Core Idea

In a standard NFA, every state transition consumes one character from the input string. An epsilon transition (written as ε or ε-transition) breaks this rule: it allows the automaton to jump from one state to another without consuming any input at all.

Think of epsilon transitions like secret hallways in a building. Normally, you move from room to room by walking through doors (consuming input). But ε-transitions are hidden passages that let you teleport between rooms instantly, without taking any steps forward.

How Epsilon Transitions Work

When an NFA is in state q and there's an ε-transition to state p, the automaton can spontaneously move to p at any time—no input symbol required. This happens in addition to all other possible transitions.

For example:

  • State A has an ε-transition to State B
  • State A also has a regular transition on symbol '0' to State C
  • When reading '0' from State A, the NFA can:
    • Go directly to C (reading the '0')
    • Jump via ε to B first, then see what B does with '0'
    • Both paths explore simultaneously

Why Use Epsilon Transitions?

Epsilon transitions make NFAs easier to design and combine. They let you "glue together" smaller automata without worrying about coordinating input symbols. They're especially useful when constructing NFAs from regular expressions—you can chain components seamlessly with ε-bridges.

Key Takeaway: Epsilon transitions allow NFAs to change states without consuming input, dramatically simplifying automaton construction while maintaining equivalent computational power to regular NFAs.