automata-theory

# Automata Theory ## What I Do I specialize in automata theory—the study of abstract computational devices and the languages they recognize. My expertise spans finite automata (DFA, NFA), regular languages, context-free grammars and pushdown automata, context-sensitive grammars, linear bounded automata, and Turing machines. I apply this theoretical foundation to design lexical analyzers, parsers, pattern matching algorithms, and to understand the fundamental limits of computation. ## When to Use Me - Designing lexical analyzers and tokenizers for compilers - Building parsers for programming languages - Implementing pattern matching and text search algorithms - Understanding computational complexity classes - Designing domain-specific languages - Analyzing protocol specifications - Proving properties about formal languages - Understanding AI/ML theoretical foundations ## Core Concepts 1. **Finite Automata**: DFA, NFA, epsilon-NFA, and their equivalence 2. **Regular Expressions**: Pattern matching, algebraic properties, Kleene star 3. **Context-Free Grammars**: Production rules, derivations, parse trees 4. **Pushdown Automata**: Stack-based computation, LALR parsing 5. **Chomsky Hierarchy**: Language classes and their properties 6. **Turing Machines**: Universal computation model, computability 7. **Decidability**: Problems that can and cannot be solved algorithmically 8. **Complexity Classes**: P, NP, PSPACE, and their relationships 9. **Closure Properties**: Operations that preserve language classes 10. **Minimization**: Reducing automata to minimal equivalent forms ## Code Examples ```python # Deterministic Finite Automaton Implementation from typing import Set, Dict, Tuple, Optional from dataclasses import dataclass from enum import Enum class Symbol: EPSILON = None @dataclass class DFA: states: Set[str] alphabet: Set[str] transitions: Dict[Tuple[str, str], str] start_state: str accept_states: Set[str] def accepts(self, input_string: str) -> bool: """Check if DFA accepts the input string.""" current = self.start_state for symbol in input_string: if (current, symbol) not in self.transitions: return False current = self.transitions[(current, symbol)] return current in self.accept_states def to_minimal_dfa(self) -> 'DFA': """Minimize DFA using Hopcroft's algorithm.""" # Initial partition: accept vs reject states P = [self.accept_states.copy(), (self.states - self.accept_states).copy()] W = [self.accept_states.copy()] while W: A = W.pop(0) for symbol in self.alphabet: # Find states that transition on symbol into A X = set() for state in self.states: if symbol in self.alphabet and (state, symbol) in self.transitions: if self.transitions[(state, symbol)] in A: X.add(state) # Refine partition new_P = [] for Y in P: intersection = X & Y difference = Y - X if intersection and difference: new_P.append(intersection) new_P.append(difference) if Y in W: W.remove(Y) W.append(intersection) W.append(difference) else: if len(intersection) <= len(difference): W.append(intersection) else: W.append(difference) else: new_P.append(Y) P = new_P # Build minimized DFA from partitions partition_map = {} for i, part in enumerate(P): for state in part: partition_map[state] = f"q{i}" new_states = {partition_map[s] for s in self.states} new_transitions = {} for (state, symbol), next_state in self.transitions.items(): new_from = partition_map[state] new_to = partition_map[next_state] new_transitions[(new_from, symbol)] = new_to new_start = partition_map[self.start_state] new_accept = {partition_map[s] for s in self.accept_states} return DFA(new_states, self.alphabet, new_transitions, new_start, new_accept) # Example: DFA for binary strings divisible by 3 def create_div_by_3_dfa() -> DFA: states = {'q0', 'q1', 'q2'} # Remainder states alphabet = {'0', '1'} transitions = { ('q0', '0'): 'q0', ('q0', '1'): 'q1', ('q1', '0'): 'q2', ('q1', '1'): 'q0', ('q2', '0'): 'q1', ('q2', '1'): 'q2', } return DFA(states, alphabet, transitions, 'q0', {'q0'}) # Test dfa = create_div_by_3_dfa() test_strings = ['0', '1', '11', '110', '1001', '10101'] for s in test_strings: print(f"{s} divisible by 3: {dfa.accepts(s)}") ``` ```python # NFA to DFA Conversion (Subset Construction) from typing import Set, Dict, List, Tuple, FrozenSet from collections import defaultdict class NFA: def __init__(self, states: Set[str], alphabet: Set[str], transitions: Dict[Tuple[str, Optional[str]], Set[str]], start_state: str, accept_states: Set[str]): self.states = states self.alphabet = alphabet self.transitions = transitions self.start_state = start_state self.accept_states = accept_states def epsilon_closure(self, states: Set[str]) -> Set[str]: """Compute epsilon closure of a set of states.""" stack = list(states) closure = set(states) while stack: state = stack.pop() key = (state, None) # epsilon transition if key in self.transitions: for next_state in self.transitions[key]: 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]: """Find states reachable from states via symbol.""" result = set() for state in states: key = (state, symbol) if key in self.transitions: result.update(self.transitions[key]) return result class DFACreator: def __init__(self, nfa: NFA): self.nfa = nfa self.dfa_states: List[FrozenSet[str]] = [] self.dfa_transitions: Dict[Tuple[int, str], int] = {} self.accept_states: Set[int] = set() self._build_dfa() def _build_dfa(self): """Build DFA using subset construction.""" start_closure = self.nfa.epsilon_closure({self.nfa.start_state}) start_set = frozenset(start_closure) self.dfa_states.append(start_set) if any(s in self.nfa.accept_states for s in start_set): self.accept_states.add(0) queue = [start_set] state_index = {start_set: 0} while queue: current_set = queue.pop(0) current_idx = state_index[current_set] for symbol in self.nfa.alphabet: # Move on symbol, then epsilon closure move_result = self.nfa.move(current_set, symbol) new_set = self.nfa.epsilon_closure(move_result) new_frozen = frozenset(new_set) if new_frozen not in state_index: new_idx = len(self.dfa_states) self.dfa_states.append(new_frozen) state_index[new_frozen] = new_idx if any(s in self.nfa.accept_states for s in new_set): self.accept_states.add(new_idx) queue.append(new_frozen) self.dfa_transitions[(current_idx, symbol)] = state_index[new_frozen] def get_dfa(self): """Return equivalent DFA.""" from .automata import DFA # Assume DFA class defined above states = {f"q{i}" for i in range(len(self.dfa_states))} start = "q0" accept = {f"q{i}" for i in self.accept_states} transitions = {} for (state_idx, symbol), next_idx in self.dfa_transitions.items(): transitions[(f"q{state_idx}", symbol)] = f"q{next_idx}" return DFA(states, self.nfa.alphabet, transitions, start, accept) # Example: NFA for (a|b)*abb def create_nfa_for_pattern() -> NFA: states = {'q0', 'q1', 'q2', 'q3'} alphabet = {'a', 'b'} transitions = { ('q0', 'a'): {'q0', 'q1'}, ('q0', 'b'): {'q0', 'q2'}, ('q1', 'b'): {'q3'}, ('q2', 'b'): {'q3'}, ('q3', None): set(), # Accepting state } return NFA(states, alphabet, transitions, 'q0', {'q3'}) nfa = create_nfa_for_pattern() creator = DFACreator(nfa) dfa = creator.get_dfa() # Test test_strings = ['abb', 'aabb', 'ababb', 'babb', 'aaabbb'] for s in test_strings: print(f"'{s}': {dfa.accepts(s)}") ``` ```python # Pushdown Automaton for Balanced Parentheses from typing import Set, Dict, Tuple, Optional, List from dataclasses import dataclass class PDA: """ Pushdown Automaton for balanced parentheses: (^n ^n) """ def __init__(self): self.states = {'q0', 'q1', 'q2'} self.alphabet = {'(', ')'} self.stack_alphabet = {'(', '$'} # Transition: (state, input, stack_top) -> [(new_state, stack_push)] self.transitions: Dict[Tuple[str, Optional[str], str], List[Tuple[str, str]]] = {} # q0: Start state self._add_transition('q0', '(', '$', 'q0', '($') self._add_transition('q0', '(', '(', 'q0', '((') # q0 -> q1 on ')', pop matching '(' self._add_transition('q0', ')', '(', 'q1', '') # q1: Still processing self._add_transition('q1', ')', '(', 'q1', '') self._add_transition('q1', None, '$', 'q2', '') # Accept on empty stack def _add_transition(self, state: str, symbol: Optional[str], stack_top: str, new_state: str, stack_push: str): key = (state, symbol, stack_top) self.transitions.setdefault(key, []).append((new_state, stack_push)) def accepts(self, input_string: str) -> bool: """Check if PDA accepts the string.""" # Each configuration: (state, stack_tuple) from collections import deque configurations = deque() configurations.append(('q0', ('$',))) # Start with bottom of stack while configurations: state, stack = configurations.pop() # If input consumed and in accept state if not input_string and state == 'q2': return True symbol = input_string[0] if input_string else None # Try transitions key = (state, symbol, stack[0] if stack else None) if key in self.transitions: for new_state, stack_push in self.transitions[key]: new_stack = stack_push[::-1] + stack[1:] if stack_push else stack[1:] new_input = input_string[1:] if symbol else input_string configurations.append((new_state, new_stack)) # Try epsilon transitions key_eps = (state, None, stack[0] if stack else None) if key_eps in self.transitions: for new_state, stack_push in self.transitions[key_eps]: new_stack = stack_push[::-1] + stack[1:] if stack_push else stack[1:] configurations.append((new_state, new_stack)) return False # Test PDA pda = PDA() test_strings = ['', '()', '(())', '(()())', '((( )))', ')(', '(()'] for s in test_strings: print(f"'{s}': {pda.accepts(s)}") ``` ## Best Practice Examples 1. **Use NFAs for Regex Matching**: Convert regex to NFA, then NFA to DFA for efficient matching 2. **Minimize Automata**: Reduce state space for efficient implementation 3. **Design Grammars Carefully**: Avoid left recursion, common prefixes for predictive parsing 4. **Check Ambiguity**: Verify grammars are unambiguous before implementation 5. **Understand Limits**: Know when a problem is undecidable or requires specific language class