オートマトン理論の概要と実装、参考図書

import re

# 正規表現を定義
TOKEN_REGEX = r"\d+|\+|-|\*|/|\(|\)"

# トークンの種類
TOKEN_TYPES = {
    r"\d+": "NUMBER",
    r"\+": "PLUS",
    r"-": "MINUS",
    r"\*": "MULTIPLY",
    r"/": "DIVIDE",
    r"\(": "LPAREN",
    r"\)": "RPAREN",
}

def tokenize(expression):
    tokens = []
    pos = 0

    while pos < len(expression):
        match = None

        for pattern, token_type in TOKEN_TYPES.items():
            regex = re.compile(pattern)
            match = regex.match(expression, pos)

            if match:
                value = match.group(0)
                tokens.append((token_type, value))
                pos = match.end()
                break

        if not match:
            raise SyntaxError("Invalid expression")

    return tokens

def parse_expression(tokens):
    return parse_add_subtract(tokens)

def parse_add_subtract(tokens):
    root = parse_multiply_divide(tokens)

    while tokens and tokens[0][0] in {"PLUS", "MINUS"}:
        operator = tokens.pop(0)
        right = parse_multiply_divide(tokens)
        root = (operator[1], root, right)

    return root

def parse_multiply_divide(tokens):
    root = parse_atom(tokens)

    while tokens and tokens[0][0] in {"MULTIPLY", "DIVIDE"}:
        operator = tokens.pop(0)
        right = parse_atom(tokens)
        root = (operator[1], root, right)

    return root

def parse_atom(tokens):
    token = tokens.pop(0)

    if token[0] == "NUMBER":
        return float(token[1])
    elif token[0] == "LPAREN":
        expression = parse_expression(tokens)
        if tokens[0][0] != "RPAREN":
            raise SyntaxError("Unbalanced parentheses")
        tokens.pop(0)
        return expression
    else:
        raise SyntaxError("Invalid expression")

def evaluate(expression):
    tokens = tokenize(expression)
    ast = parse_expression(tokens)
    return evaluate_ast(ast)

def evaluate_ast(ast):
    if isinstance(ast, float):
        return ast
    else:
        operator, left, right = ast
        if operator == "PLUS":
            return evaluate_ast(left) + evaluate_ast(right)
        elif operator == "MINUS":
            return evaluate_ast(left) - evaluate_ast(right)
        elif operator == "MULTIPLY":
            return evaluate_ast(left) * evaluate_ast(right)
        elif operator == "DIVIDE":
            return evaluate_ast(left) / evaluate_ast(right)

expression = "3 + (4 * 5 - 6) / 2"
result = evaluate(expression)
print(result)  # Output: 8.0

class AuthenticationProtocolFSM:
    def __init__(self):
        self.state = "INITIAL"
        
    def transition(self, event):
        if self.state == "INITIAL" and event == "SEND_PASSWORD":
            self.state = "PASSWORD_SENT"
        elif self.state == "PASSWORD_SENT" and event == "PASSWORD_OK":
            self.state = "AUTHENTICATED"
        else:
            raise ValueError("Invalid event in current state")

    def is_authenticated(self):
        return self.state == "AUTHENTICATED"

# シミュレーション
def simulate_authentication_protocol(password):
    fsm = AuthenticationProtocolFSM()

    # クライアントがパスワードを送信
    fsm.transition("SEND_PASSWORD")

    # サーバーがパスワードを検証
    if password == "secure_password":
        fsm.transition("PASSWORD_OK")

    return fsm.is_authenticated()

# 認証プロトコルのシミュレーション
password = "secure_password"
result = simulate_authentication_protocol(password)
if result:
    print("Authentication successful!")
else:
    print("Authentication failed!")

import random

class ProbabilisticFiniteAutomaton:
    def __init__(self, transition_probs):
        self.states = len(transition_probs)
        self.transition_probs = transition_probs
        self.current_state = 0

    def transition(self):
        probabilities = self.transition_probs[self.current_state]
        next_state = random.choices(range(self.states), probabilities)[0]
        self.current_state = next_state

class ControlSystem:
    def __init__(self):
        self.pfa = ProbabilisticFiniteAutomaton([[0.9, 0.1], [0.3, 0.7]])

    def control(self, input_signal):
        # ランダムな確率有限オートマトンの遷移を行う
        self.pfa.transition()

        # 現在の状態に基づいて制御を行う
        current_state = self.pfa.current_state
        if current_state == 0:
            return input_signal
        elif current_state == 1:
            return -input_signal

def simulate_control_system(num_iterations):
    control_sys = ControlSystem()
    input_signal = 1

    for _ in range(num_iterations):
        output_signal = control_sys.control(input_signal)
        print(f"Input Signal: {input_signal}, Output Signal: {output_signal}")

# 自動制御システムのシミュレーション
num_iterations = 10
simulate_control_system(num_iterations)

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

# トライを使用した文字列検索の例
trie = Trie()
words = ["apple", "app", "banana", "orange", "grape"]

for word in words:
    trie.insert(word)

# 単語の検索
print(trie.search("apple"))     # True
print(trie.search("banana"))    # True
print(trie.search("pear"))      # False

# 接頭辞の検索
print(trie.starts_with("app"))  # True
print(trie.starts_with("gr"))   # True
print(trie.starts_with("pea"))  # False

class FiniteAutomaton:
    def __init__(self, pattern):
        self.pattern = pattern
        self.states = len(pattern) + 1
        self.transitions = self.compute_transitions()

    def compute_transitions(self):
        transitions = [{} for _ in range(self.states)]
        for state in range(self.states):
            for char in set(self.pattern):
                next_state = min(self.states, state + 1)
                while next_state > 0 and not (self.pattern[:next_state] + char).endswith(self.pattern[:next_state]):
                    next_state -= 1
                transitions[state][char] = next_state
        return transitions

    def match(self, text):
        state = 0
        for char in text:
            state = self.transitions[state].get(char, 0)
            if state == self.states - 1:
                return True
        return False

# 文字列パターンマッチングの例
pattern = "ababc"
fa = FiniteAutomaton(pattern)

text = "abababcde"
if fa.match(text):
    print("Pattern found in the text.")
else:
    print("Pattern not found in the text.")

class QueryOptimizer:
    def __init__(self, query):
        self.query = query

    def optimize_query(self):
        parts = self.query.split(" OR ")
        if len(parts) > 1:
            optimized_query = "|".join(f"({part})" for part in parts)
            return optimized_query
        return self.query

# クエリ最適化の例
query = "A OR B OR C OR D"
optimizer = QueryOptimizer(query)
optimized_query = optimizer.optimize_query()
print(f"Original Query: {query}")
print(f"Optimized Query: {optimized_query}")