Epsilon-NFA Implementation

Epsilon-NFA Implementation Visually

Learn Epsilon-NFA implementation with interactive examples. Understand epsilon transitions, closure operations, and non-deterministic computation.

Visual Simulation Step Execution Epsilon-NFA Constructor Performance Analysis

What is an Epsilon-NFA (ε-NFA)?

An Epsilon-NFA (ε-NFA) is a Non-deterministic Finite Automaton that allows epsilon (ε) transitions - transitions that can be taken without consuming any input symbol. This makes ε-NFAs even more flexible than regular NFAs for representing regular languages.

An ε-NFA 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)
  • q₀: Initial state (q₀ ∈ Q)
  • F: Set of final/accepting states (F ⊆ Q)
Key Concept - Epsilon Closure (ε-closure): thE ε-closure of a state q is thE set of all states reachable from q using only ε-transitions (including q itself).

Example ε-NFA

ε-NFA that accepts strings ending with "01" over alphabet {0, 1}

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

ε-NFA Implementation

class wwr: def __init__(self, states, alphabet, transitions, start_state, final_states): self.states = states self.alphabet = alphabet self.transitions = transitions self.start_state = start_state self.final_states = final_states def epsilon_closure(self, states): """Compute epsilon closure of a set of states""" closure = set(states) stack = list(states) while stack: state = stack.pop() if state in self.transitions and 'ε' in self.transitions[state]: for next_state in self.transitions[state]['ε']: if next_state not in closure: closure.add(next_state) stack.append(next_state) return closure def process_string(self, input_string): current_states = self.epsilon_closure({self.start_state}) trace = [list(current_states)] for symbol in input_string: if symbol not in self.alphabet: return False, "Invalid symbol", trace next_states = set() for state in current_states: if state in self.transitions and symbol in self.transitions[state]: next_states.update(self.transitions[state][symbol]) # Apply epsilon closure to next states current_states = self.epsilon_closure(next_states) trace.append(list(current_states)) if not current_states: break # Check if any current state is final accepted = bool(current_states.intersection(self.final_states)) return accepted, current_states, trace # Example ε-NFA for strings ending with "01" epsilon_nfa = wwr( states={'q0', 'q1', 'q2', 'q3'}, alphabet={'0', '1'}, transitions={ 'q0': {'0': {'q0'}, '1': {'q0'}, 'ε': {'q1'}}, 'q1': {'0': {'q2'}}, 'q2': {'1': {'q3'}}, 'q3': {} }, start_state='q0', final_states={'q3'} )

Epsilon Closure Algorithm

thE epsilon closure is fundamental to ε-NFA processing:

def epsilon_closure_detailed(self, states): """Detailed epsilon closure computation with steps""" closure = set(states) stack = list(states) steps = [f"Initial states: {{{', '.join(sorted(states))}@}}"] while stack: current = stack.pop() steps.append(f"Processing state: {{current@}}") if current in self.transitions and 'ε' in self.transitions[current]: epsilon_transitions = self.transitions[current]['ε'] steps.append(f" ε-transitions from {{current@}}: {{{', '.join(sorted(epsilon_transitions))}@}}") for next_state in epsilon_transitions: if next_state not in closure: closure.add(next_state) stack.append(next_state) steps.append(f" Added {{next_state@}} to closure") else: steps.append(f" {{next_state@}} already in closure") else: steps.append(f" No ε-transitions from {{current@}}") steps.append(f"Final ε-closure: {{{', '.join(sorted(closure))}@}}") return closure, steps

Custom ε-NFA Builder

Build your own ε-NFA with epsilon transitions and test strings

ε-NFA Configuration
Transition Function (including ε-transitions)

Enhanced ε-NFA Simulator

Test strings with detailed epsilon closure visualization

1x
Mode:
0ms Avg Time
0 ε-Closures
O(1) Complexity

ε-NFA Statistics

States: 4
Transitions: 5
ε-Transitions: 1
Alphabet Size: 2
Tests Run: 0
Acceptance Rate: 0%
Quick Test Strings
ε-Closure Calculator

Visual ε-NFA Diagram

Batch Testing with ε-Closure Analysis

Test multiple strings and analyze epsilon closure behavior

ε-NFA to NFA Conversion

See how thE current ε-NFA can be converted to an equivalent NFA