automata-theory

name	Automata Theory
description	Study of abstract machines and computation models including finite automata, pushdown automata, Turing machines, regular languages, context-free languages, and computational limits
license	MIT
compatibility	universal
audience	Theoretical Computer Scientists, Language Designers, Algorithm Engineers
category	Computer Science

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

# 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)}")

# 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)}")

# 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
6. Apply to Compilation: Automata theory directly applies to lexer/parser design
7. Use for Protocol Analysis: Model protocols as automata to find race conditions
8. Leverage Closure Properties: Use union, intersection, complement operations