Finite Automata
NFA Simulator
Simulate and test nondeterministic finite automata with interactive visualizations
NFA Simulator
Nondeterministic Finite Automata (NFA) can be in multiple states simultaneously
Non-Deterministic Finite Automaton (NFA) 🌟
Multiple paths and parallel processing - explore all possibilities simultaneously
NFA Characteristics
Key Differences from DFA
Transition Function
δ: Q × Σ → 2^Q (Power set of Q)
Returns a set of states, not just one state like DFA
Interactive NFA Simulator
NFA State Diagram
Initial
State
Branch 1
Branch 2
Final
ACCEPT
Transition Table
| State | 0 | 1 |
|---|---|---|
| q₀ | {q₀, q₁} | {q₀, q₂} |
| q₁ | {q₃} | ∅ |
| q₂ | {q₂, q₃} | {q₃} |
| q₃ | {q₃} | {q₃} |
String Processing: "11001"
Example Strings
Reaches final state q3
Multiple paths lead to q3
Non-deterministic choice succeeds
Complex path through multiple states
No path reaches final state
NFA vs DFA Comparison
DFA (Deterministic)
✓ One transition per input symbol
✓ Single current state
✓ Predictable execution
✓ Easier to implement
✗ May require more states
NFA (Non-Deterministic)
✓ Multiple transitions per input
✓ Set of current states
✓ More expressive power
✓ Often fewer states needed
✗ More complex to simulate