CampusFlow

DFA Simulator

Deterministic Finite Automaton — Interactive Visualization

Click "Add State" to begin building your DFA

States

Transitions

Click source then destination, enter symbol

Examples

Simulation

Theory & Reference

What is a DFA?

A Deterministic Finite Automaton (DFA) is a 5-tuple (Q, Σ, δ, q₀, F) where:

  • Q — finite set of states
  • Σ — finite input alphabet
  • δ: Q × Σ → Q — transition function (deterministic)
  • q₀ ∈ Q — start state
  • F ⊆ Q — set of accept (final) states

A DFA reads the input string left to right, one symbol at a time. At each step, it follows exactly one transition based on current state and input symbol. If after consuming all input the machine is in an accept state, the string is accepted.

Common Interview Questions

Q1: What is the difference between DFA and NFA?

DFA has exactly one transition per input symbol from each state; NFA can have 0, 1, or multiple. NFA allows ε-transitions. Every NFA can be converted to an equivalent DFA (exponential blowup possible).

Q2: What languages cannot be recognized by a DFA?

Non-regular languages like aⁿbⁿ (equal counts) or palindromes require memory beyond finite states. The Pumping Lemma is used to prove a language is not regular.

Q3: How do you minimize a DFA?

Merge indistinguishable states using the table-filling algorithm. Two states are distinguishable if one is accepting and the other is not, or if for some symbol they transition to distinguishable states. Repeat until no more merges.

Real-World Applications

  • Lexical analysis in compilers (token recognition)
  • Vending machines and protocol verification
  • Text search (regex engines, grep)
  • Digital circuit design (sequential logic)
  • Network intrusion detection (pattern matching)