Finite Automata
DFA Simulator
Simulate and test deterministic finite automata with interactive visualizations
DFA Simulator
Deterministic Finite Automata (DFA) are the simplest computational models with finite memory
Deterministic Finite Automaton (DFA) 🤖
Single path decision making - one clear transition for each input symbol
DFA Definition & Example
5-Tuple Definition
M = (Q, Σ, δ, q₀, F)
Q = {q₀, q₁, q₂, q₃} (finite set of states)
Σ = {0, 1} (input alphabet)
δ = Q × Σ → Q (transition function)
q₀ = q₀ ∈ Q (initial state)
F = {q₂} ⊆ Q (set of final states)
Language Description
L(M) = {w ∈ {0,1}* | w has odd number of 0's and even number of 1's}
Examples: {ε, 0, 011, 101, 110, 000, 01111, 00011, ...}
Transition Table δ(q, a)
| State | Input: 0 | Input: 1 |
|---|---|---|
| →q₀ | q₂ | q₁ |
| q₁ | q₃ | q₀ |
| *q₂ | q₀ | q₃ |
| q₃ | q₁ | q₂ |
→ = initial state, * = final state
Interactive DFA Simulator
DFA State Diagram
Even 0's
Even 1's
START
Even 0's
Odd 1's
Odd 0's
Even 1's
ACCEPT
Odd 0's
Odd 1's
Transitions: q₀ --0--> q₂, q₀ --1--> q₁, q₁ --0--> q₃, q₁ --1--> q₀, q₂ --0--> q₀, q₂ --1--> q₃, q₃ --0--> q₁, q₃ --1--> q₂
String Processing: "01111"
Example Strings
One 0 (odd), zero 1's (even)
One 0 (odd), two 1's (even)
One 0 (odd), two 1's (even)
One 0 (odd), two 1's (even)
Two 0's (even), three 1's (odd)
One 0 (odd), four 1's (even)