NeuralBlitz What I do
- Implement finite automata
- Design regular expressions
- Build parsers and lexers
- Understand computational limits
When to use me
When building text processors, lexical analyzers, or pattern matchers.
Finite Automata
Deterministic Finite Automaton
from typing import Set, Dict
class DFA:
"""Deterministic Finite Automaton"""
def __init__(self, states: Set[str], alphabet: Set[str],
transition: Dict[str, Dict[str, str]],
start_state: str, accept_states: Set[str]):
self.states = states
self.alphabet = alphabet
self.transition = transition
self.start_state = start_state
self.accept_states = accept_states
def accept(self, input_string: str) -> bool:
"""Check if DFA accepts input"""
current = self.start_state
for symbol in input_string:
if symbol not in self.alphabet:
return False
if current not in self.transition:
return False
if symbol not in self.transition[current]:
return False
current = self.transition[current][symbol]
return current in self.accept_states
def simulate(self, input_string: str) -> Dict:
"""Simulate DFA and return trace"""
trace = [{"state": self.start_state, "input": ""}]
current = self.start_state
for i, symbol in enumerate(input_string):
if current in self.transition and symbol in self.transition[current]:
current = self.transition[current][symbol]
trace.append({"state": current, "input": input_string[:i+1]})
return {
"accepted": current in self.accept_states,
"final_state": current,
"trace": trace
}
# Example: Binary strings divisible by 3
divisible_by_3_dfa = DFA(
states={"q0", "q1", "q2"},
alphabet={"0", "1"},
transition={
"q0": {"0": "q0", "1": "q1"},
"q1": {"0": "q2", "1": "q0"},
"q2": {"0": "q1", "1": "q2"}
},
start_state="q0",
accept_states={"q0"}
)
Nondeterministic Finite Automaton
class NFA:
"""Nondeterministic Finite Automaton"""
def __init__(self, states: Set[str], alphabet: Set[str],
transition: Dict[str, Dict[str, Set[str]]],
epsilon_transition: Dict[str, Set[str]],
start_state: str, accept_states: Set[str]):
self.states = states
self.alphabet = alphabet
self.transition = transition
self.epsilon_transition = epsilon_transition
self.start_state = start_state
self.accept_states = accept_states
def epsilon_closure(self, states: Set[str]) -> Set[str]:
"""Compute epsilon closure of states"""
closure = set(states)
stack = list(states)
while stack:
state = stack.pop()
if state in self.epsilon_transition:
for next_state in self.epsilon_transition[state]:
if next_state not in closure:
closure.add(next_state)
stack.append(next_state)
return closure
def move(self, states: Set[str], symbol: str) -> Set[str]:
"""Compute move operation"""
result = set()
for state in states:
if state in self.transition and symbol in self.transition[state]:
result.update(self.transition[state][symbol])
return result
def accept(self, input_string: str) -> bool:
"""Check if NFA accepts input"""
current = self.epsilon_closure({self.start_state})
for symbol in input_string:
current = self.epsilon_closure(self.move(current, symbol))
return bool(current & self.accept_states)
Regular Expressions to NFA (Thompson's Construction)
class RegexToNFA:
"""Convert regex to NFA using Thompson's construction"""
def __init__(self):
self.state_counter = 0
def create_state(self) -> str:
"""Create unique state"""
state = f"q{self.state_counter}"
self.state_counter += 1
return state
def build_nfa(self, regex: str) -> NFA:
"""Build NFA from regex"""
# Simplified: parse and build NFA
# In practice, use proper regex parser
pass
def union(self, nfa1: NFA, nfa2: NFA) -> NFA:
"""Union of two NFAs"""
start = self.create_state()
accept = self.create_state()
new_transition = {}
new_transition[start] = {"": {nfa1.start_state, nfa2.start_state}}
# Connect accept states to new accept
for state in nfa1.accept_states:
if state not in new_transition:
new_transition[state] = {}
new_transition[state][""] = {accept}
return NFA(
states="...",
alphabet="...",
transition=new_transition,
epsilon_transition="...",
start_state=start,
accept_states={accept}
)
Pushdown Automaton
class PDA:
"""Pushdown Automaton for context-free languages"""
def __init__(self, states: Set[str], alphabet: Set[str],
stack_alphabet: Set[str],
transition: Dict[str, Dict[str, Dict[str, tuple]]],
start_state: str, accept_states: Set[str]):
self.states = states
self.alphabet = alphabet
self.stack_alphabet = stack_alphabet
self.transition = transition
self.start_state = start_state
self.accept_states = accept_states
def accept(self, input_string: str, mode: str = "final") -> bool:
"""Check if PDA accepts input"""
stack = ["$"]
state = self.start_state
input_pos = 0
while input_pos <= len(input_string):
# Try epsilon transition
if self._epsilon_transition(state, stack):
state, stack = self._apply_transition(
state, "", stack, "ε"
)
# Try symbol transition
if input_pos < len(input_string):
symbol = input_string[input_pos]
if self._symbol_transition(state, symbol, stack):
state, stack = self._apply_transition(
state, symbol, stack, symbol
)
input_pos += 1
# Check for acceptance
if input_pos == len(input_string) and state in self.accept_states:
return True
return False