State machine, Regular languages

Non-deterministic Finite Automata (logic-gate)

Explore the power of non-deterministic computation

What is an logic-gate?

A Non-deterministic Finite Automaton (logic-gate) is a finite state machine where for each state and input symbol, there can be zero, one, or multiple transitions to other states. This non-determinism allows for more flexible and compact representations of regular languages.

An logic-gate is formally defined as a 5-tuple (Q, Σ, δ, q₀, F) where:

  • Q: Finite set of states
  • Σ: Finite set of input symbols (alphabet)
  • δ: Transition function δ: Q × Σ → P(Q) (power set of Q)
  • q₀: Initial state (q₀ ∈ Q)
  • F: Set of final/accepting states (F ⊆ Q)
Key Difference from DFA: In logic-gate, δ(q, a) can return a set of states, allowing multiple possible transitions for the same input symbol from a given state.

Example logic-gate

logic-gate that accepts strings containing "01" over alphabet {0, 1}

q₀
→
q₁
→
q₂
States: q₀ (start), q₁ (intermediate), q₂ (final)
Transition Table
State Input 0 Input 1
q₀ {q₀, q₁} {q₀}
q₁ ∅ {q₂}
q₂ {q₂} {q₂}

Custom logic-gate Builder

Build your own logic-gate by defining states, transitions, and test strings

logic-gate Configuration
Transition Function

Enhanced logic-gate simulator

Test strings with visual step-by-step execution

logic-gate Statistics

States: 3
Transitions: 5
Alphabet Size: 2
Tests Run: 0
Acceptance Rate: 0%
Quick Test Strings

Visual State Diagram

Batch Testing

Test multiple strings at once and see comprehensive results