S → SS | (S) | ε

E → E + T | T
T → T * F | F
F → id | (E)

D(<M>):
    运行 H(<M>, <M>)
    如果 H 接受，则进入无限循环
    如果 H 拒绝，则停机并接受

import re

# 邮箱验证
pattern = r'^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$'
if re.match(pattern, email):
    ...

# 注意：正则表达式不能匹配嵌套结构
# 如需匹配HTML标签，需要使用解析器

class ConnectionState:
    DISCONNECTED = 0
    CONNECTING = 1
    CONNECTED = 2
    DISCONNECTING = 3

class Connection:
    def __init__(self):
        self.state = ConnectionState.DISCONNECTED
    
    def connect(self):
        if self.state == ConnectionState.DISCONNECTED:
            self.state = ConnectionState.CONNECTING
            # 开始连接...
    
    def on_connected(self):
        if self.state == ConnectionState.CONNECTING:
            self.state = ConnectionState.CONNECTED

# 简单的算术表达式解析（递归下降）
def parse_expression(tokens):
    # 使用CFG规则解析
    pass

# 使用Z3求解器
from z3 import *

x, y, z = Bools('x y z')
solver = Solver()
solver.add(Or(x, y))
solver.add(Or(Not(x), z))
solver.add(Or(Not(y), Not(z)))

if solver.check() == sat:
    print(solver.model())

"""
有限状态机实现
"""


class DFA:
    """确定性有限自动机"""
    
    def __init__(self, states, alphabet, transitions, start_state, accept_states):
        """
        初始化DFA
        
        参数:
            states: 状态集合
            alphabet: 字母表
            transitions: 转移函数字典 {(state, symbol): next_state}
            start_state: 初始状态
            accept_states: 接受状态集合
        """
        self.states = states
        self.alphabet = alphabet
        self.transitions = transitions
        self.start_state = start_state
        self.accept_states = set(accept_states)
    
    def accepts(self, input_string):
        """判断是否接受输入字符串"""
        current_state = self.start_state
        
        for symbol in input_string:
            if symbol not in self.alphabet:
                return False
            current_state = self.transitions.get((current_state, symbol))
            if current_state is None:
                return False
        
        return current_state in self.accept_states


def demonstrate_dfa():
    """演示DFA"""
    
    # 识别以"01"结尾的二进制字符串
    dfa = DFA(
        states={'q0', 'q1', 'q2'},
        alphabet={'0', '1'},
        transitions={
            ('q0', '0'): 'q1', ('q0', '1'): 'q0',
            ('q1', '0'): 'q1', ('q1', '1'): 'q2',
            ('q2', '0'): 'q1', ('q2', '1'): 'q0',
        },
        start_state='q0',
        accept_states={'q2'}
    )
    
    print("=== DFA：识别以'01'结尾的字符串 ===")
    
    test_strings = ["01", "001", "101", "0101", "0", "1", "10", "11"]
    
    for s in test_strings:
        result = dfa.accepts(s)
        print(f"  '{s}': {'接受' if result else '拒绝'}")


if __name__ == "__main__":
    demonstrate_dfa()

"""
简化版正则表达式匹配器
支持: . * + ?
"""


def match_regex(pattern, text):
    """
    简化的正则表达式匹配
    
    支持:
    . : 匹配任意字符
    * : 前一个字符重复0次或多次
    + : 前一个字符重复1次或多次
    ? : 前一个字符重复0次或1次
    """
    
    def match_here(regex, txt):
        """在txt的开头匹配regex"""
        if not regex:
            return True
        if regex == '$':
            return not txt
        
        # 处理下一个字符是量词的情况
        if len(regex) > 1:
            if regex[1] == '*':
                return match_star(regex[0], regex[2:], txt)
            if regex[1] == '+':
                return match_plus(regex[0], regex[2:], txt)
            if regex[1] == '?':
                return match_question(regex[0], regex[2:], txt)
        
        # 匹配单个字符
        if txt and (regex[0] == '.' or regex[0] == txt[0]):
            return match_here(regex[1:], txt[1:])
        
        return False
    
    def match_star(char, regex, txt):
        """处理 * 量词"""
        for i in range(len(txt) + 1):
            if match_here(regex, txt[i:]):
                return True
            if i < len(txt) and char != '.' and txt[i] != char:
                break
        return False
    
    def match_plus(char, regex, txt):
        """处理 + 量词"""
        if not txt or (char != '.' and txt[0] != char):
            return False
        return match_star(char, regex, txt[1:])
    
    def match_question(char, regex, txt):
        """处理 ? 量词"""
        # 0次
        if match_here(regex, txt):
            return True
        # 1次
        if txt and (char == '.' or txt[0] == char):
            return match_here(regex, txt[1:])
        return False
    
    # 尝试在每个位置匹配
    for i in range(len(text) + 1):
        if match_here(pattern, text[i:]):
            return True
    
    return False


def demonstrate_regex():
    """演示正则表达式匹配"""
    
    print("=== 简化正则表达式匹配 ===")
    
    tests = [
        ("a*b", "aaab", True),
        ("a*b", "b", True),
        ("a+b", "b", False),
        ("a+b", "ab", True),
        ("a?b", "b", True),
        ("a?b", "ab", True),
        ("a?b", "aab", False),
        (".*", "anything", True),
        ("hel.o", "hello", True),
    ]
    
    for pattern, text, expected in tests:
        result = match_regex(pattern, text)
        status = "✓" if result == expected else "✗"
        print(f"  '{pattern}' vs '{text}': {result} {status}")


if __name__ == "__main__":
    demonstrate_regex()

"""
简单图灵机模拟器
"""


class TuringMachine:
    """图灵机模拟器"""
    
    def __init__(self, states, alphabet, tape_alphabet, transitions, start_state, blank_symbol, accept_state, reject_state):
        self.states = states
        self.alphabet = alphabet
        self.tape_alphabet = tape_alphabet
        self.transitions = transitions  # {(state, symbol): (new_state, new_symbol, direction)}
        self.start_state = start_state
        self.blank_symbol = blank_symbol
        self.accept_state = accept_state
        self.reject_state = reject_state
    
    def run(self, input_string, max_steps=1000):
        """
        运行图灵机
        
        返回: ('accept', steps), ('reject', steps), 或 ('loop', max_steps)
        """
        # 初始化纸带
        tape = list(input_string)
        if not tape:
            tape = [self.blank_symbol]
        
        head_pos = 0
        state = self.start_state
        steps = 0
        
        while steps < max_steps:
            steps += 1
            
            # 读取当前符号
            if head_pos >= len(tape):
                tape.extend([self.blank_symbol] * (head_pos - len(tape) + 1))
            
            current_symbol = tape[head_pos]
            
            # 查找转移
            transition = self.transitions.get((state, current_symbol))
            if transition is None:
                return ('reject', steps)
            
            new_state, new_symbol, direction = transition
            
            # 写入新符号
            tape[head_pos] = new_symbol
            
            # 移动读写头
            if direction == 'L':
                head_pos -= 1
                if head_pos < 0:
                    tape.insert(0, self.blank_symbol)
                    head_pos = 0
            elif direction == 'R':
                head_pos += 1
            
            # 更新状态
            state = new_state
            
            if state == self.accept_state:
                return ('accept', steps)
            if state == self.reject_state:
                return ('reject', steps)
        
        return ('loop', max_steps)


def demonstrate_turing_machine():
    """演示图灵机"""
    
    # 识别 {a^n b^n | n >= 0} 的图灵机
    tm = TuringMachine(
        states={'q0', 'q1', 'q2', 'q3', 'q_accept', 'q_reject'},
        alphabet={'a', 'b'},
        tape_alphabet={'a', 'b', 'X', 'Y', '_'},
        transitions={
            # q0: 找a
            ('q0', 'a'): ('q1', 'X', 'R'),  # 标记a为X
            ('q0', 'Y'): ('q3', 'Y', 'R'),  # 所有a都处理完了
            ('q0', '_'): ('q_accept', '_', 'R'),  # 空串接受
            
            # q1: 向右跳过a和Y
            ('q1', 'a'): ('q1', 'a', 'R'),
            ('q1', 'Y'): ('q1', 'Y', 'R'),
            ('q1', 'b'): ('q2', 'Y', 'L'),  # 找到b，标记为Y
            
            # q2: 向左跳回
            ('q2', 'a'): ('q2', 'a', 'L'),
            ('q2', 'Y'): ('q2', 'Y', 'L'),
            ('q2', 'X'): ('q0', 'X', 'R'),  # 回到起点
            
            # q3: 验证后面没有a
            ('q3', 'Y'): ('q3', 'Y', 'R'),
            ('q3', '_'): ('q_accept', '_', 'R'),
        },
        start_state='q0',
        blank_symbol='_',
        accept_state='q_accept',
        reject_state='q_reject'
    )
    
    print("=== 图灵机：识别 a^n b^n ===")
    
    test_inputs = ["", "ab", "aabb", "aaabbb", "aab", "abb", "abc"]
    
    for inp in test_inputs:
        result, steps = tm.run(inp)
        status = "接受" if result == 'accept' else "拒绝" if result == 'reject' else "循环"
        print(f"  '{inp}': {status} ({steps}步)")


if __name__ == "__main__":
    demonstrate_turing_machine()