Automata Theory

class DFA:
    def __init__(self, states, alphabet, transitions, start, accept):
        self.states = states
        self.alphabet = alphabet
        self.transitions = transitions
        self.start = start
        self.accept = accept

    def accepts(self, string):
        state = self.start
        for char in string:
            state = self.transitions.get((state, char))
            if state is None:
                return False
        return state in self.accept

    def minimize_states(self):
        # Simple state equivalence check
        reachable = self.get_reachable_states()
        return len(reachable)

    def get_reachable_states(self):
        visited = set()
        stack = [self.start]
        while stack:
            state = stack.pop()
            if state in visited:
                continue
            visited.add(state)
            for symbol in self.alphabet:
                next_state = self.transitions.get((state, symbol))
                if next_state and next_state not in visited:
                    stack.append(next_state)
        return visited

# DFA for strings ending in 'ab'
dfa = DFA(
    states={'q0', 'q1', 'q2'},
    alphabet={'a', 'b'},
    transitions={
        ('q0', 'a'): 'q1', ('q0', 'b'): 'q0',
        ('q1', 'a'): 'q1', ('q1', 'b'): 'q2',
        ('q2', 'a'): 'q1', ('q2', 'b'): 'q0',
    },
    start='q0',
    accept={'q2'}
)

test_strings = ["aab", "ab", "ba", "baba", ""]
for s in test_strings:
    print(f"'{s}' -> {dfa.accepts(s)}")

class NFA:
    def __init__(self, states, alphabet, transitions, start, accept):
        self.states = states
        self.alphabet = alphabet
        self.transitions = transitions
        self.start = start
        self.accept = accept

    def epsilon_closure(self, states):
        closure = set(states)
        stack = list(states)
        while stack:
            state = stack.pop()
            for next_state in self.transitions.get((state, ''), []):
                if next_state not in closure:
                    closure.add(next_state)
                    stack.append(next_state)
        return closure

    def move(self, states, symbol):
        result = set()
        for state in states:
            result.update(self.transitions.get((state, symbol), []))
        return result

    def accepts(self, string):
        current = self.epsilon_closure({self.start})
        for char in string:
            current = self.epsilon_closure(self.move(current, char))
        return bool(current & self.accept)

    def to_dfa(self):
        dfa_states = {}
        dfa_transitions = {}
        start_closure = frozenset(self.epsilon_closure({self.start}))
        dfa_states[start_closure] = 'D0'
        state_counter = 1
        unmarked = [start_closure]

        while unmarked:
            current = unmarked.pop()
            current_name = dfa_states[current]
            for symbol in self.alphabet:
                next_set = frozenset(self.epsilon_closure(self.move(current, symbol)))
                if next_set and next_set not in dfa_states:
                    dfa_states[next_set] = f'D{state_counter}'
                    state_counter += 1
                    unmarked.append(next_set)
                if next_set:
                    dfa_transitions[(current_name, symbol)] = dfa_states[next_set]

        dfa_accept = {name for states, name in dfa_states.items() if states & self.accept}
        return dfa_states[start_closure], dfa_transitions, dfa_accept

# NFA for strings containing 'ab'
nfa = NFA(
    states={'q0', 'q1', 'q2'},
    alphabet={'a', 'b'},
    transitions={
        ('q0', 'a'): {'q0', 'q1'},
        ('q0', 'b'): {'q0'},
        ('q1', 'b'): {'q2'},
    },
    start='q0',
    accept={'q2'}
)

for s in ["ab", "cab", "ba", "abc"]:
    print(f"'{s}' -> {nfa.accepts(s)}")

import re

def regex_match(pattern, string):
    return bool(re.fullmatch(pattern, string))

# Common patterns
patterns = {
    'even_0s': r'^[1]*(0[1]*0[1]*)*$',
    'div_by_3': r'^(0|1(01*0)*1)*$',
    'contains_ab': r'^.*ab.*$',
    'binary_length_even': r'^(0|1)*$',
}

for name, pat in patterns.items():
    test = "11001"
    print(f"{name}: {regex_match(pat, test)}")

class TuringMachine:
    def __init__(self, transitions, start, accept, reject, blank='_'):
        self.transitions = transitions
        self.start = start
        self.accept = accept
        self.reject = reject
        self.blank = blank

    def run(self, tape, max_steps=1000):
        tape = list(tape)
        head = 0
        state = self.start
        steps = 0

        while steps < max_steps:
            if state == self.accept:
                return True, ''.join(tape).strip(self.blank)
            if state == self.reject:
                return False, ''.join(tape).strip(self.blank)

            symbol = tape[head] if head < len(tape) else self.blank
            if (state, symbol) not in self.transitions:
                return False, ''.join(tape).strip(self.blank)

            new_state, new_symbol, direction = self.transitions[(state, symbol)]
            if head < len(tape):
                tape[head] = new_symbol
            else:
                tape.append(new_symbol)

            if direction == 'R':
                head += 1
                if head >= len(tape):
                    tape.append(self.blank)
            else:
                head = max(0, head - 1)

            state = new_state
            steps += 1

        return False, 'Max steps exceeded'

# TM that increments a binary number
tm = TuringMachine(
    transitions={
        ('q0', '0'): ('q0', '0', 'R'),
        ('q0', '1'): ('q0', '1', 'R'),
        ('q0', '_'): ('q1', '_', 'L'),
        ('q1', '0'): ('q2', '1', 'L'),
        ('q1', '1'): ('q1', '0', 'L'),
        ('q1', '_'): ('q2', '1', 'L'),
    },
    start='q0',
    accept='q2',
    reject='q3'
)

accepted, result = tm.run("1011")
print(f"Input: 1011, Output: {result}, Accepted: {accepted}")