import time
import matplotlib.pyplot as plt
import numpy as np

class AsymptoticAnalyzer:
    """漸近記法の実験的検証クラス"""
    
    def __init__(self):
        self.results = {}
    
    def measure_time(self, func, input_generator, sizes, trials=5):
        """アルゴリズムの実行時間測定"""
        times = []
        
        for n in sizes:
            trial_times = []
            
            for _ in range(trials):
                data = input_generator(n)
                
                start_time = time.perf_counter()
                func(data)
                end_time = time.perf_counter()
                
                trial_times.append(end_time - start_time)
            
            # 中央値を採用（外れ値の影響を軽減）
            times.append(np.median(trial_times))
        
        return times
    
    def analyze_complexity(self, algorithm_name, func, input_gen, 
                          theoretical_complexity, max_size=1000):
        """計算量の理論値と実測値を比較"""
        sizes = [2**i for i in range(5, int(np.log2(max_size)) + 1)]
        times = self.measure_time(func, input_gen, sizes)
        
        # 理論値の計算
        theoretical_times = []
        for n in sizes:
            if theoretical_complexity == "O(1)":
                theoretical_times.append(1)
            elif theoretical_complexity == "O(log n)":
                theoretical_times.append(np.log2(n))
            elif theoretical_complexity == "O(n)":
                theoretical_times.append(n)
            elif theoretical_complexity == "O(n log n)":
                theoretical_times.append(n * np.log2(n))
            elif theoretical_complexity == "O(n^2)":
                theoretical_times.append(n**2)
            elif theoretical_complexity == "O(2^n)":
                theoretical_times.append(2**n if n <= 20 else float('inf'))
        
        # 正規化（最初の値で割る）
        if times[0] > 0:
            normalized_times = [t / times[0] for t in times]
        if theoretical_times[0] > 0:
            normalized_theoretical = [t / theoretical_times[0] for t in theoretical_times]
        
        self.results[algorithm_name] = {
            'sizes': sizes,
            'measured': normalized_times,
            'theoretical': normalized_theoretical,
            'complexity': theoretical_complexity
        }
    
    def plot_results(self):
        """結果をプロット"""
        plt.figure(figsize=(12, 8))
        
        for name, data in self.results.items():
            plt.loglog(data['sizes'], data['measured'], 'o-', 
                      label=f"{name} (measured)")
            plt.loglog(data['sizes'], data['theoretical'], '--', 
                      label=f"{name} {data['complexity']} (theoretical)")
        
        plt.xlabel('Input Size (n)')
        plt.ylabel('Normalized Time')
        plt.title('Algorithm Complexity Analysis')
        plt.legend()
        plt.grid(True)
        plt.show()

# 使用例
def bubble_sort(arr):
    """バブルソート O(n²)"""
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

def merge_sort(arr):
    """マージソート O(n log n)"""
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def linear_search(arr, target):
    """線形探索 O(n)"""
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

def binary_search(arr, target):
    """二分探索 O(log n)"""
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

# 実験実行例
if __name__ == "__main__":
    analyzer = AsymptoticAnalyzer()
    
    # ランダム配列生成器
    def random_array(n):
        return np.random.randint(0, 1000, n).tolist()
    
    # ソート済み配列生成器
    def sorted_array(n):
        return list(range(n))
    
    # 各アルゴリズムの解析
    analyzer.analyze_complexity("Bubble Sort", bubble_sort, random_array, "O(n^2)", 500)
    analyzer.analyze_complexity("Merge Sort", merge_sort, random_array, "O(n log n)", 2000)
    
    # 探索アルゴリズム用のラッパー
    def linear_search_wrapper(arr):
        return linear_search(arr, arr[-1] if arr else 0)
    
    def binary_search_wrapper(arr):
        sorted_arr = sorted(arr)
        return binary_search(sorted_arr, sorted_arr[-1] if sorted_arr else 0)
    
    analyzer.analyze_complexity("Linear Search", linear_search_wrapper, random_array, "O(n)", 2000)
    analyzer.analyze_complexity("Binary Search", binary_search_wrapper, random_array, "O(log n)", 2000)
    
    # 結果をプロット
    analyzer.plot_results()

import math
from typing import Callable, Tuple

class MasterTheoremAnalyzer:
    """Master定理の適用と検証"""
    
    @staticmethod
    def analyze_recurrence(a: int, b: int, f_complexity: str) -> str:
        """
        T(n) = aT(n/b) + f(n) の形の漸化式を Master定理で解析
        
        Args:
            a: 再帰呼び出しの回数
            b: 問題サイズの分割数
            f_complexity: f(n)の複雑度 ("n^k", "n^k log n", "n^k log^j n")
        
        Returns:
            解の複雑度
        """
        # n^(log_b a) を計算
        critical_exponent = math.log(a) / math.log(b)
        
        # f(n)の指数を解析
        if "log" not in f_complexity:
            # f(n) = n^k の場合
            k = float(f_complexity.split("^")[1]) if "^" in f_complexity else 1.0
            
            if k < critical_exponent:
                return f"Θ(n^{critical_exponent:.2f})"
            elif k == critical_exponent:
                return f"Θ(n^{k} log n)"
            else:  # k > critical_exponent
                return f"Θ({f_complexity})"
        else:
            # f(n) = n^k log^j n の場合
            # 簡略化のため、k = critical_exponent の場合のみ扱う
            return f"Θ(n^{critical_exponent:.2f} log^2 n)"
    
    @staticmethod
    def verify_with_substitution(recurrence_func: Callable, n_max: int = 1000):
        """代入法による検証"""
        memo = {}
        
        def solve(n):
            if n in memo:
                return memo[n]
            
            if n <= 1:
                memo[n] = 1
                return 1
            
            result = recurrence_func(n, solve)
            memo[n] = result
            return result
        
        # 実行時間測定
        sizes = [2**i for i in range(1, int(math.log2(n_max)) + 1)]
        times = []
        
        for n in sizes:
            memo.clear()  # メモをクリア
            result = solve(n)
            times.append(result)
        
        return sizes, times

# 具体例の実装

def merge_sort_recurrence(n, solve):
    """マージソートの漸化式 T(n) = 2T(n/2) + n"""
    if n <= 1:
        return 1
    return 2 * solve(n // 2) + n

def karatsuba_recurrence(n, solve):
    """Karatsuba法の漸化式 T(n) = 3T(n/2) + n"""
    if n <= 1:
        return 1
    return 3 * solve(n // 2) + n

def strassen_recurrence(n, solve):
    """Strassen法の漸化式 T(n) = 7T(n/2) + n²"""
    if n <= 1:
        return 1
    return 7 * solve(n // 2) + n*n

# 使用例
if __name__ == "__main__":
    analyzer = MasterTheoremAnalyzer()
    
    # Master定理による解析
    print("Master定理による解析:")
    print("マージソート T(n) = 2T(n/2) + n:", 
          analyzer.analyze_recurrence(2, 2, "n"))
    print("Karatsuba T(n) = 3T(n/2) + n:", 
          analyzer.analyze_recurrence(3, 2, "n"))
    print("Strassen T(n) = 7T(n/2) + n²:", 
          analyzer.analyze_recurrence(7, 2, "n^2"))
    
    # 数値的検証
    print("\n数値的検証:")
    sizes, merge_times = analyzer.verify_with_substitution(merge_sort_recurrence, 256)
    print("マージソート実測値（最後の数値）:", merge_times[-3:])
    
    # 理論値との比較
    theoretical_merge = [n * math.log2(n) for n in sizes[-3:]]
    print("理論値 n log n:", [f"{t:.1f}" for t in theoretical_merge])

from typing import Dict, Tuple, Set, Optional
from enum import Enum

class Direction(Enum):
    LEFT = "L"
    RIGHT = "R"

class TuringMachine:
    """チューリング機械のシミュレータ"""
    
    def __init__(self, 
                 states: Set[str],
                 alphabet: Set[str],
                 tape_alphabet: Set[str],
                 transitions: Dict[Tuple[str, str], Tuple[str, str, Direction]],
                 start_state: str,
                 accept_state: str,
                 reject_state: str,
                 blank_symbol: str = '␣'):
        
        self.states = states
        self.alphabet = alphabet
        self.tape_alphabet = tape_alphabet
        self.transitions = transitions
        self.start_state = start_state
        self.accept_state = accept_state
        self.reject_state = reject_state
        self.blank_symbol = blank_symbol
        
        # 実行時の状態
        self.current_state = start_state
        self.tape = []
        self.head_position = 0
        self.step_count = 0
        
    def initialize(self, input_string: str):
        """入力文字列で機械を初期化"""
        self.current_state = self.start_state
        self.tape = list(input_string) + [self.blank_symbol]
        self.head_position = 0
        self.step_count = 0
        
    def step(self) -> bool:
        """1ステップ実行。終了状態に到達したらFalseを返す"""
        if self.current_state in [self.accept_state, self.reject_state]:
            return False
        
        # 現在の記号を読む
        if self.head_position >= len(self.tape):
            self.tape.extend([self.blank_symbol] * (self.head_position - len(self.tape) + 1))
        
        current_symbol = self.tape[self.head_position]
        
        # 遷移規則を確認
        if (self.current_state, current_symbol) not in self.transitions:
            self.current_state = self.reject_state
            return False
        
        next_state, write_symbol, direction = self.transitions[(self.current_state, current_symbol)]
        
        # 状態更新
        self.tape[self.head_position] = write_symbol
        self.current_state = next_state
        
        # ヘッド移動
        if direction == Direction.LEFT:
            if self.head_position > 0:
                self.head_position -= 1
            else:
                self.tape = [self.blank_symbol] + self.tape
                # head_position は 0 のまま
        else:  # RIGHT
            self.head_position += 1
            if self.head_position >= len(self.tape):
                self.tape.append(self.blank_symbol)
        
        self.step_count += 1
        return True
    
    def run(self, input_string: str, max_steps: int = 10000) -> Tuple[str, int, str]:
        """
        入力文字列で機械を実行
        
        Returns:
            (結果, ステップ数, 最終テープ内容)
        """
        self.initialize(input_string)
        
        while self.step() and self.step_count < max_steps:
            pass
        
        if self.step_count >= max_steps:
            result = "TIMEOUT"
        elif self.current_state == self.accept_state:
            result = "ACCEPT"
        else:
            result = "REJECT"
        
        # テープの内容を文字列として返す（末尾の空白を除去）
        tape_content = ''.join(self.tape).rstrip(self.blank_symbol)
        
        return result, self.step_count, tape_content
    
    def get_configuration(self) -> str:
        """現在の構成を文字列で返す"""
        left_part = ''.join(self.tape[:self.head_position])
        right_part = ''.join(self.tape[self.head_position+1:])
        current_symbol = self.tape[self.head_position] if self.head_position < len(self.tape) else self.blank_symbol
        
        return f"{left_part}{self.current_state}{current_symbol}{right_part}"

# 具体例1: {0^n 1^n | n ≥ 0} を認識する機械
def create_equal_zeros_ones_tm():
    """同数の0と1を認識するTMを作成"""
    states = {"q1", "q2", "q3", "q4", "q5", "qaccept", "qreject"}
    alphabet = {"0", "1"}
    tape_alphabet = {"0", "1", "x", "y", "␣"}
    
    transitions = {
        # 0をxに変えて1を探しに行く
        ("q1", "0"): ("q2", "x", Direction.RIGHT),
        ("q1", "y"): ("q1", "y", Direction.RIGHT),
        ("q1", "␣"): ("qaccept", "␣", Direction.RIGHT),
        
        # 0と1をスキップして1を探す
        ("q2", "0"): ("q2", "0", Direction.RIGHT),
        ("q2", "y"): ("q2", "y", Direction.RIGHT),
        ("q2", "1"): ("q3", "y", Direction.LEFT),
        
        # 左端に戻る
        ("q3", "0"): ("q3", "0", Direction.LEFT),
        ("q3", "y"): ("q3", "y", Direction.LEFT),
        ("q3", "x"): ("q1", "x", Direction.RIGHT),
        
        # エラー処理
        ("q1", "1"): ("qreject", "1", Direction.RIGHT),
        ("q2", "␣"): ("qreject", "␣", Direction.RIGHT),
    }
    
    return TuringMachine(
        states=states,
        alphabet=alphabet,
        tape_alphabet=tape_alphabet,
        transitions=transitions,
        start_state="q1",
        accept_state="qaccept",
        reject_state="qreject"
    )

# 具体例2: 文字列を逆順にする機械
def create_string_reverser_tm():
    """文字列を逆順にするTMを作成"""
    states = {"q1", "q2", "q3", "q4", "qaccept"}
    alphabet = {"0", "1"}
    tape_alphabet = {"0", "1", "␣"}
    
    transitions = {
        # 最右端に移動
        ("q1", "0"): ("q1", "0", Direction.RIGHT),
        ("q1", "1"): ("q1", "1", Direction.RIGHT),
        ("q1", "␣"): ("q2", "␣", Direction.LEFT),
        
        # 一文字ずつ左端に移動
        ("q2", "0"): ("q3", "␣", Direction.LEFT),
        ("q2", "1"): ("q4", "␣", Direction.LEFT),
        ("q2", "␣"): ("qaccept", "␣", Direction.RIGHT),
        
        # 0を左端に配置
        ("q3", "0"): ("q3", "0", Direction.LEFT),
        ("q3", "1"): ("q3", "1", Direction.LEFT),
        ("q3", "␣"): ("q1", "0", Direction.RIGHT),
        
        # 1を左端に配置
        ("q4", "0"): ("q4", "0", Direction.LEFT),
        ("q4", "1"): ("q4", "1", Direction.LEFT),
        ("q4", "␣"): ("q1", "1", Direction.RIGHT),
    }
    
    return TuringMachine(
        states=states,
        alphabet=alphabet,
        tape_alphabet=tape_alphabet,
        transitions=transitions,
        start_state="q1",
        accept_state="qaccept",
        reject_state="qaccept"  # この機械は必ず停止する
    )

# 使用例とテスト
if __name__ == "__main__":
    # {0^n 1^n | n ≥ 0} テスト
    print("=== 同数の0と1を認識するTM ===")
    tm1 = create_equal_zeros_ones_tm()
    
    test_cases = ["", "01", "0011", "000111", "0101", "001"]
    for test in test_cases:
        result, steps, final_tape = tm1.run(test)
        print(f"入力: '{test}' → 結果: {result} ({steps} steps)")
    
    # 文字列逆順テスト
    print("\n=== 文字列を逆順にするTM ===")
    tm2 = create_string_reverser_tm()
    
    test_cases = ["0", "01", "101", "0011", "11010"]
    for test in test_cases:
        result, steps, final_tape = tm2.run(test)
        print(f"入力: '{test}' → 出力: '{final_tape}' ({steps} steps)")

import json
from typing import Any, Dict

class UniversalTuringMachine:
    """万能チューリング機械の実装"""
    
    def __init__(self):
        self.blank = "␣"
    
    def encode_machine(self, tm: TuringMachine) -> str:
        """チューリング機械を文字列として符号化"""
        encoding = {
            "states": list(tm.states),
            "alphabet": list(tm.alphabet),
            "tape_alphabet": list(tm.tape_alphabet),
            "transitions": {},
            "start_state": tm.start_state,
            "accept_state": tm.accept_state,
            "reject_state": tm.reject_state,
            "blank_symbol": tm.blank_symbol
        }
        
        # 遷移関数を文字列キーで符号化
        for (state, symbol), (next_state, write_symbol, direction) in tm.transitions.items():
            key = f"{state},{symbol}"
            encoding["transitions"][key] = [next_state, write_symbol, direction.value]
        
        return json.dumps(encoding)
    
    def decode_machine(self, encoded: str) -> TuringMachine:
        """符号化された文字列からチューリング機械を復元"""
        data = json.loads(encoded)
        
        # 遷移関数を復元
        transitions = {}
        for key, (next_state, write_symbol, direction_str) in data["transitions"].items():
            state, symbol = key.split(",", 1)
            direction = Direction.LEFT if direction_str == "L" else Direction.RIGHT
            transitions[(state, symbol)] = (next_state, write_symbol, direction)
        
        return TuringMachine(
            states=set(data["states"]),
            alphabet=set(data["alphabet"]),
            tape_alphabet=set(data["tape_alphabet"]),
            transitions=transitions,
            start_state=data["start_state"],
            accept_state=data["accept_state"],
            reject_state=data["reject_state"],
            blank_symbol=data["blank_symbol"]
        )
    
    def simulate(self, encoded_machine: str, input_string: str, max_steps: int = 10000):
        """万能機械として符号化された機械をシミュレート"""
        # 機械を復元
        tm = self.decode_machine(encoded_machine)
        
        # シミュレーション実行
        result, steps, final_tape = tm.run(input_string, max_steps)
        
        return {
            "result": result,
            "steps": steps,
            "final_tape": final_tape,
            "original_machine": encoded_machine,
            "input": input_string
        }

# 使用例
if __name__ == "__main__":
    # 万能機械の作成
    utm = UniversalTuringMachine()
    
    # テスト用の機械を符号化
    tm = create_equal_zeros_ones_tm()
    encoded = utm.encode_machine(tm)
    
    print("=== 万能チューリング機械の実演 ===")
    print(f"符号化された機械の長さ: {len(encoded)} 文字")
    print(f"符号化の一部: {encoded[:100]}...")
    
    # 万能機械でシミュレーション
    test_inputs = ["", "01", "0011", "000111", "001"]
    
    for input_str in test_inputs:
        result = utm.simulate(encoded, input_str)
        print(f"入力: '{input_str}' → 結果: {result['result']} ({result['steps']} steps)")
    
    # 別の機械でもテスト
    print("\n=== 別の機械での実演 ===")
    reverser = create_string_reverser_tm()
    encoded_reverser = utm.encode_machine(reverser)
    
    for input_str in ["01", "101", "0011"]:
        result = utm.simulate(encoded_reverser, input_str)
        print(f"入力: '{input_str}' → 出力: '{result['final_tape']}' ({result['steps']} steps)")

from typing import Set, Dict, Tuple, List, Optional
from collections import defaultdict

class DFA:
    """決定性有限オートマトン"""
    
    def __init__(self, 
                 states: Set[str],
                 alphabet: Set[str],
                 transitions: Dict[Tuple[str, str], 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 accepts(self, string: str) -> bool:
        """文字列を受理するかチェック"""
        current_state = self.start_state
        
        for symbol in string:
            if symbol not in self.alphabet:
                return False
            
            if (current_state, symbol) not in self.transitions:
                return False
            
            current_state = self.transitions[(current_state, symbol)]
        
        return current_state in self.accept_states
    
    def trace_execution(self, string: str) -> List[str]:
        """実行過程をトレース"""
        trace = [self.start_state]
        current_state = self.start_state
        
        for symbol in string:
            if (current_state, symbol) in self.transitions:
                current_state = self.transitions[(current_state, symbol)]
                trace.append(current_state)
            else:
                trace.append("REJECT")
                break
        
        return trace

class NFA:
    """非決定性有限オートマトン"""
    
    def __init__(self,
                 states: Set[str],
                 alphabet: Set[str],
                 transitions: Dict[Tuple[str, 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]:
        """ε-閉包を計算（ここでは実装簡略化のため省略）"""
        return states
    
    def accepts(self, string: str) -> bool:
        """文字列を受理するかチェック（部分集合構成法）"""
        current_states = {self.start_state}
        
        for symbol in string:
            next_states = set()
            
            for state in current_states:
                if (state, symbol) in self.transitions:
                    next_states.update(self.transitions[(state, symbol)])
            
            current_states = next_states
            
            if not current_states:  # デッドエンド
                return False
        
        # 受理状態との交差をチェック
        return bool(current_states & self.accept_states)
    
    def to_dfa(self) -> DFA:
        """部分集合構成法でDFAに変換"""
        # 状態の部分集合を表現（簡略化のため文字列として）
        def states_to_string(state_set: Set[str]) -> str:
            return '{' + ','.join(sorted(state_set)) + '}'
        
        def string_to_states(state_str: str) -> Set[str]:
            if state_str == '{}':
                return set()
            return set(state_str[1:-1].split(',')) if state_str != '{}' else set()
        
        dfa_states = set()
        dfa_transitions = {}
        dfa_accept_states = set()
        
        # 初期状態
        start_set = {self.start_state}
        start_str = states_to_string(start_set)
        dfa_start = start_str
        
        # 幅優先で新しい状態を探索
        queue = [start_set]
        visited = {start_str}
        
        while queue:
            current_set = queue.pop(0)
            current_str = states_to_string(current_set)
            dfa_states.add(current_str)
            
            # 受理状態かチェック
            if current_set & self.accept_states:
                dfa_accept_states.add(current_str)
            
            # 各記号に対する遷移
            for symbol in self.alphabet:
                next_set = set()
                
                for state in current_set:
                    if (state, symbol) in self.transitions:
                        next_set.update(self.transitions[(state, symbol)])
                
                next_str = states_to_string(next_set)
                dfa_transitions[(current_str, symbol)] = next_str
                
                if next_str not in visited:
                    visited.add(next_str)
                    queue.append(next_set)
        
        return DFA(
            states=dfa_states,
            alphabet=self.alphabet,
            transitions=dfa_transitions,
            start_state=dfa_start,
            accept_states=dfa_accept_states
        )

# 具体例の実装

def create_even_zeros_dfa() -> DFA:
    """偶数個の0を含む文字列を認識するDFA"""
    return DFA(
        states={"q0", "q1"},
        alphabet={"0", "1"},
        transitions={
            ("q0", "0"): "q1",
            ("q0", "1"): "q0",
            ("q1", "0"): "q0",
            ("q1", "1"): "q1"
        },
        start_state="q0",
        accept_states={"q0"}
    )

def create_ends_with_01_nfa() -> NFA:
    """01で終わる文字列を認識するNFA"""
    return NFA(
        states={"q0", "q1", "q2"},
        alphabet={"0", "1"},
        transitions={
            ("q0", "0"): {"q0", "q1"},
            ("q0", "1"): {"q0"},
            ("q1", "0"): set(),
            ("q1", "1"): {"q2"},
            ("q2", "0"): {"q1"},
            ("q2", "1"): {"q0"}
        },
        start_state="q0",
        accept_states={"q2"}
    )

# テストとデモンストレーション
if __name__ == "__main__":
    print("=== DFA: 偶数個の0を含む文字列 ===")
    dfa = create_even_zeros_dfa()
    
    test_strings = ["", "1", "0", "01", "00", "101", "1001", "0110"]
    for s in test_strings:
        result = dfa.accepts(s)
        trace = dfa.trace_execution(s)
        print(f"'{s}': {result} (trace: {' → '.join(trace)})")
    
    print("\n=== NFA: 01で終わる文字列 ===")
    nfa = create_ends_with_01_nfa()
    
    test_strings = ["01", "101", "001", "11", "010", "1001", ""]
    for s in test_strings:
        result = nfa.accepts(s)
        print(f"'{s}': {result}")
    
    print("\n=== NFA to DFA 変換 ===")
    converted_dfa = nfa.to_dfa()
    print(f"NFAの状態数: {len(nfa.states)}")
    print(f"変換後のDFAの状態数: {len(converted_dfa.states)}")
    print("DFAの状態:", converted_dfa.states)
    
    # 変換結果の検証
    print("\n変換結果の検証:")
    for s in test_strings:
        nfa_result = nfa.accepts(s)
        dfa_result = converted_dfa.accepts(s)
        match = "✓" if nfa_result == dfa_result else "✗"
        print(f"'{s}': NFA={nfa_result}, DFA={dfa_result} {match}")

import re
from typing import Union, Optional
from abc import ABC, abstractmethod

class RegexAST(ABC):
    """正規表現の抽象構文木の基底クラス"""
    
    @abstractmethod
    def to_nfa(self) -> NFA:
        """NFAに変換"""
        pass
    
    @abstractmethod
    def __str__(self) -> str:
        pass

class CharNode(RegexAST):
    """文字ノード"""
    
    def __init__(self, char: str):
        self.char = char
    
    def to_nfa(self) -> NFA:
        """文字を認識するNFAを構成"""
        return NFA(
            states={"q0", "q1"},
            alphabet={self.char},
            transitions={("q0", self.char): {"q1"}},
            start_state="q0",
            accept_states={"q1"}
        )
    
    def __str__(self) -> str:
        return self.char

class ConcatNode(RegexAST):
    """連結ノード"""
    
    def __init__(self, left: RegexAST, right: RegexAST):
        self.left = left
        self.right = right
    
    def to_nfa(self) -> NFA:
        """2つのNFAを連結"""
        left_nfa = self.left.to_nfa()
        right_nfa = self.right.to_nfa()
        
        # 状態の名前を区別するために接頭辞を追加
        def rename_states(nfa: NFA, prefix: str) -> NFA:
            new_states = {f"{prefix}_{s}" for s in nfa.states}
            new_transitions = {}
            for (state, symbol), next_states in nfa.transitions.items():
                new_key = (f"{prefix}_{state}", symbol)
                new_transitions[new_key] = {f"{prefix}_{s}" for s in next_states}
            
            return NFA(
                states=new_states,
                alphabet=nfa.alphabet,
                transitions=new_transitions,
                start_state=f"{prefix}_{nfa.start_state}",
                accept_states={f"{prefix}_{s}" for s in nfa.accept_states}
            )
        
        left_renamed = rename_states(left_nfa, "L")
        right_renamed = rename_states(right_nfa, "R")
        
        # 結合
        states = left_renamed.states | right_renamed.states
        alphabet = left_renamed.alphabet | right_renamed.alphabet
        transitions = {**left_renamed.transitions, **right_renamed.transitions}
        
        # 左の受理状態から右の開始状態へのε遷移を追加（簡略化のため省略）
        # 実際の実装では、ε遷移を使用するか、受理状態を統合する
        
        return NFA(
            states=states,
            alphabet=alphabet,
            transitions=transitions,
            start_state=left_renamed.start_state,
            accept_states=right_renamed.accept_states
        )
    
    def __str__(self) -> str:
        return f"({self.left}{self.right})"

class UnionNode(RegexAST):
    """和集合ノード"""
    
    def __init__(self, left: RegexAST, right: RegexAST):
        self.left = left
        self.right = right
    
    def to_nfa(self) -> NFA:
        """2つのNFAの和集合を構成"""
        # 実装省略（Thompsonの構成法を使用）
        pass
    
    def __str__(self) -> str:
        return f"({self.left}|{self.right})"

class StarNode(RegexAST):
    """クリーネ閉包ノード"""
    
    def __init__(self, expr: RegexAST):
        self.expr = expr
    
    def to_nfa(self) -> NFA:
        """Kleene閉包のNFAを構成"""
        # 実装省略（Thompsonの構成法を使用）
        pass
    
    def __str__(self) -> str:
        return f"({self.expr})*"

class SimpleRegexEngine:
    """簡単な正規表現エンジン"""
    
    def __init__(self):
        self.compiled_patterns = {}
    
    def compile(self, pattern: str) -> DFA:
        """正規表現をDFAにコンパイル（簡略化された実装）"""
        if pattern in self.compiled_patterns:
            return self.compiled_patterns[pattern]
        
        # 非常に簡単なパターンのみサポート
        if pattern == "0*":
            # 0の繰り返し
            dfa = DFA(
                states={"q0"},
                alphabet={"0", "1"},
                transitions={
                    ("q0", "0"): "q0"
                },
                start_state="q0",
                accept_states={"q0"}
            )
        elif pattern == "(01)*":
            # 01の繰り返し
            dfa = DFA(
                states={"q0", "q1"},
                alphabet={"0", "1"},
                transitions={
                    ("q0", "0"): "q1",
                    ("q1", "1"): "q0"
                },
                start_state="q0",
                accept_states={"q0"}
            )
        else:
            # デフォルト: 何も受理しない
            dfa = DFA(
                states={"qrej"},
                alphabet={"0", "1"},
                transitions={},
                start_state="qrej",
                accept_states=set()
            )
        
        self.compiled_patterns[pattern] = dfa
        return dfa
    
    def match(self, pattern: str, string: str) -> bool:
        """正規表現にマッチするかチェック"""
        dfa = self.compile(pattern)
        return dfa.accepts(string)
    
    def find_matches(self, pattern: str, string: str) -> List[str]:
        """文字列中のマッチ箇所を検索"""
        matches = []
        
        # すべての部分文字列をチェック（非効率だが簡単）
        for i in range(len(string) + 1):
            for j in range(i, len(string) + 1):
                substring = string[i:j]
                if self.match(pattern, substring):
                    matches.append(substring)
        
        return matches

# 使用例とテスト
if __name__ == "__main__":
    print("=== 簡単な正規表現エンジン ===")
    engine = SimpleRegexEngine()
    
    # パターンのテスト
    patterns = ["0*", "(01)*"]
    test_strings = ["", "0", "00", "01", "0101", "010", "1", "001"]
    
    for pattern in patterns:
        print(f"\nパターン: {pattern}")
        for string in test_strings:
            result = engine.match(pattern, string)
            print(f"  '{string}': {result}")
    
    # 標準ライブラリとの比較
    print("\n=== Python標準ライブラリとの比較 ===")
    import re
    
    # より複雑なパターンをPythonのreモジュールでテスト
    python_patterns = [
        (r"^0*$", "0の繰り返し"),
        (r"^(01)*$", "01の繰り返し"),
        (r"^[01]*$", "0と1の任意の組み合わせ"),
        (r"1.*1", "1で始まり1で終わる")
    ]
    
    test_strings = ["", "0", "00", "01", "0101", "010", "1", "001", "101", "111"]
    
    for pattern, description in python_patterns:
        print(f"\nパターン: {pattern} ({description})")
        compiled_pattern = re.compile(pattern)
        for string in test_strings:
            result = bool(compiled_pattern.match(string))
            print(f"  '{string}': {result}")

from typing import List, Set, Tuple, Optional
import networkx as nx

class DecidabilityExamples:
    """決定可能問題の実装例集"""
    
    @staticmethod
    def dfa_acceptance_problem(dfa_description: dict, input_string: str) -> bool:
        """
        DFA受理問題 A_DFA の実装
        A_DFA = {<B, w> | B は DFA で、B は w を受理する}
        """
        try:
            # DFAの形式チェック
            required_keys = ['states', 'alphabet', 'transitions', 'start_state', 'accept_states']
            for key in required_keys:
                if key not in dfa_description:
                    return False
            
            # DFAを構築
            dfa = DFA(
                states=set(dfa_description['states']),
                alphabet=set(dfa_description['alphabet']),
                transitions=dfa_description['transitions'],
                start_state=dfa_description['start_state'],
                accept_states=set(dfa_description['accept_states'])
            )
            
            # 文字列を受理するかチェック
            return dfa.accepts(input_string)
            
        except Exception:
            return False
    
    @staticmethod
    def cfg_emptiness_problem(cfg_description: dict) -> bool:
        """
        CFG空性問題 E_CFG の実装
        E_CFG = {<G> | G は CFG で、L(G) = ∅}
        """
        try:
            variables = set(cfg_description['variables'])
            terminals = set(cfg_description['terminals'])
            rules = cfg_description['rules']
            start_symbol = cfg_description['start_symbol']
            
            # 有用な変数を計算（終端記号を生成可能な変数）
            useful_vars = set()
            
            # 反復的に有用な変数を見つける
            changed = True
            while changed:
                changed = False
                for lhs, rhs in rules:
                    if lhs not in useful_vars:
                        # 右辺がすべて終端記号または有用な変数か？
                        if all(symbol in terminals or symbol in useful_vars for symbol in rhs):
                            useful_vars.add(lhs)
                            changed = True
            
            # 開始記号が有用でなければ空言語
            return start_symbol not in useful_vars
            
        except Exception:
            return True  # エラーの場合は空と判定
    
    @staticmethod
    def graph_connectivity_problem(graph_description: dict) -> bool:
        """
        グラフ連結性問題 CONNECTED の実装
        CONNECTED = {<G> | G は連結グラフ}
        """
        try:
            vertices = graph_description['vertices']
            edges = graph_description['edges']
            
            if not vertices:
                return True  # 空グラフは連結
            
            # グラフを構築
            G = nx.Graph()
            G.add_nodes_from(vertices)
            G.add_edges_from(edges)
            
            # 連結性をチェック
            return nx.is_connected(G)
            
        except Exception:
            return False
    
    @staticmethod
    def prime_testing_problem(n: int) -> bool:
        """
        素数判定問題 PRIME の実装
        PRIME = {n | n は素数}
        """
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        
        # 試し割り法（決定的多項式時間アルゴリズム）
        i = 3
        while i * i <= n:
            if n % i == 0:
                return False
            i += 2
        
        return True
    
    @staticmethod
    def linear_equation_solvability(coefficients: List[List[float]], 
                                   constants: List[float]) -> bool:
        """
        線形方程式系の解の存在問題
        システム Ax = b が解を持つかどうか
        """
        try:
            import numpy as np
            
            A = np.array(coefficients)
            b = np.array(constants)
            
            # 拡大行列の階数と係数行列の階数を比較
            rank_A = np.linalg.matrix_rank(A)
            rank_Ab = np.linalg.matrix_rank(np.column_stack([A, b]))
            
            # Rouché-Capelliの定理
            return rank_A == rank_Ab
            
        except Exception:
            return False

class UndecidabilityExamples:
    """決定不能問題の例（シミュレーション）"""
    
    @staticmethod
    def halting_problem_simulator(tm_description: dict, input_string: str, 
                                 max_steps: int = 1000) -> Optional[bool]:
        """
        停止問題のシミュレータ（制限された時間で実行）
        実際の停止問題は決定不能だが、制限時間内での近似判定
        """
        try:
            # TMを実装（簡略化）
            tm = TuringMachine(
                states=set(tm_description['states']),
                alphabet=set(tm_description['alphabet']),
                tape_alphabet=set(tm_description['tape_alphabet']),
                transitions=tm_description['transitions'],
                start_state=tm_description['start_state'],
                accept_state=tm_description['accept_state'],
                reject_state=tm_description['reject_state']
            )
            
            result, steps, _ = tm.run(input_string, max_steps)
            
            if result in ["ACCEPT", "REJECT"]:
                return True  # 停止した
            else:
                return None  # タイムアウト（不明）
                
        except Exception:
            return None
    
    @staticmethod
    def post_correspondence_problem(dominoes: List[Tuple[str, str]], 
                                   max_length: int = 10) -> Optional[List[int]]:
        """
        Post対応問題の制限された探索
        決定不能だが、限られた長さまでは探索可能
        """
        def check_sequence(sequence: List[int]) -> bool:
            top = ''.join(dominoes[i][0] for i in sequence)
            bottom = ''.join(dominoes[i][1] for i in sequence)
            return top == bottom
        
        # 深さ優先探索（制限された深さ）
        def dfs(current_sequence: List[int], depth: int) -> Optional[List[int]]:
            if depth > max_length:
                return None
            
            if current_sequence and check_sequence(current_sequence):
                return current_sequence
            
            for i in range(len(dominoes)):
                result = dfs(current_sequence + [i], depth + 1)
                if result:
                    return result
            
            return None
        
        return dfs([], 0)

# テストとデモンストレーション
if __name__ == "__main__":
    print("=== 決定可能問題の実装例 ===")
    
    # DFA受理問題
    print("1. DFA受理問題:")
    dfa_desc = {
        'states': ['q0', 'q1'],
        'alphabet': ['0', '1'],
        'transitions': {('q0', '0'): 'q1', ('q0', '1'): 'q0', 
                       ('q1', '0'): 'q0', ('q1', '1'): 'q1'},
        'start_state': 'q0',
        'accept_states': ['q0']
    }
    
    test_strings = ['', '0', '00', '01', '11']
    for s in test_strings:
        result = DecidabilityExamples.dfa_acceptance_problem(dfa_desc, s)
        print(f"  DFA accepts '{s}': {result}")
    
    # CFG空性問題
    print("\n2. CFG空性問題:")
    cfg_desc = {
        'variables': ['S', 'A'],
        'terminals': ['a', 'b'],
        'rules': [('S', ['A', 'A']), ('A', ['a'])],
        'start_symbol': 'S'
    }
    
    is_empty = DecidabilityExamples.cfg_emptiness_problem(cfg_desc)
    print(f"  CFG generates empty language: {is_empty}")
    
    # グラフ連結性問題
    print("\n3. グラフ連結性問題:")
    graph_desc = {
        'vertices': ['a', 'b', 'c', 'd'],
        'edges': [('a', 'b'), ('b', 'c'), ('c', 'd')]
    }
    
    is_connected = DecidabilityExamples.graph_connectivity_problem(graph_desc)
    print(f"  Graph is connected: {is_connected}")
    
    # 素数判定問題
    print("\n4. 素数判定問題:")
    test_numbers = [17, 25, 97, 100, 101]
    for n in test_numbers:
        is_prime = DecidabilityExamples.prime_testing_problem(n)
        print(f"  {n} is prime: {is_prime}")
    
    print("\n=== 決定不能問題の近似例 ===")
    
    # 停止問題のシミュレーション
    print("1. 停止問題シミュレーション:")
    simple_tm = {
        'states': ['q1', 'qaccept', 'qreject'],
        'alphabet': ['0', '1'],
        'tape_alphabet': ['0', '1', '␣'],
        'transitions': {
            ('q1', '0'): ('qaccept', '0', Direction.RIGHT),
            ('q1', '1'): ('qreject', '1', Direction.RIGHT),
        },
        'start_state': 'q1',
        'accept_state': 'qaccept',
        'reject_state': 'qreject'
    }
    
    test_inputs = ['0', '1', '']
    for inp in test_inputs:
        result = UndecidabilityExamples.halting_problem_simulator(simple_tm, inp)
        print(f"  TM halts on '{inp}': {result}")
    
    # Post対応問題
    print("\n2. Post対応問題:")
    dominoes = [('ab', 'a'), ('a', 'ab'), ('b', 'bb')]
    solution = UndecidabilityExamples.post_correspondence_problem(dominoes)
    print(f"  Solution found: {solution}")
    
    if solution:
        top = ''.join(dominoes[i][0] for i in solution)
        bottom = ''.join(dominoes[i][1] for i in solution)
        print(f"  Top: {top}, Bottom: {bottom}")