NFA で正規演算

graphviz.py

def tweak_q(q):
    if "States" in str(q):
        return str(q).replace("States", "").replace(".", "_")
    else:
        return f"q{q}"


def generate_dot(nfa, name="sample"):
    """ Graphviz でそのまま出力できるテキスト"""
    result = ""
    result += "digraph sample {\n"
    # すべてを円にする
    result += "\tnode [ shape = circle ];\n"
    result += "\tq0 [ shape = point ];\n"
    # 開始状態
    result += f"""\tq0 -> {tweak_q(nfa.start_state)};\n"""

    from_to_labels = {}
    for tran, states in nfa.transition_pair.items():
        q_from, a = tran
        for q_to in states:
            # １つ状態から同じ遷移先の場合、ラベルを1つにしたいため
            labels = from_to_labels.get((q_from, q_to), [])
            labels += "ε" if a == "" else a
            from_to_labels[(q_from, q_to)] = labels

    # ラベルを結合して、出力
    for from_to_q, labels in from_to_labels.items():
        q_from, q_to = from_to_q
        label = ','.join(labels)
        result += f"""\t{tweak_q(q_from)} -> {tweak_q(q_to)} [label = "{label}"];\n"""

    for q in nfa.accept_states:
        result += f"""\t{tweak_q(q)} [ shape = doublecircle ];\n"""
    result += "}"
    return result

nfa.py

"""
NFA
"""
from functools import reduce


class NFA:
    def __init__(
        self, states, alphabets, start_state, accept_states, transition_pair,
    ):
        self.states = states
        self.alphabets = alphabets
        self.start_state = start_state
        self.accept_states = accept_states

        # 和集合演算するときに使うため、ここで関数を生成するようにしてみた
        self.transition_pair = transition_pair
        # 関数の生成
        # 遷移関数
        self.transition = make_transition(transition_pair)
        # 空列での遷移関数 (開始状態にも使いたいため、こうした)
        self.E = make_E(transition_pair)

    def run(self, input_str: str) -> bool:
        """ 入力文字列を読み出し、受理するかどうかを返す
        """
        # その時時の状態は集合で表す
        # 毎回、リセット
        self.cur_states = self.E(set({self.start_state}))

        for s in input_str:
            # 各状態に対して、遷移関数を適用し、和集合演算する
            # print(f"{s}: {self.cur_states} ==> ", end="")
            _states = set()
            for q in self.cur_states:
                _states = _states.union(self.E(self.transition(q, s)))
            self.cur_states = _states
            # print(self.cur_states)

        # 受理状態が含まれていた場合、True
        return not self.accept_states.isdisjoint(self.cur_states)



def make_transition(tran_pair):
    """ 遷移関数を返す関数 """

    def transition_method(q, a):
        # E を適用
        return tran_pair.get((q, a), {})

    return transition_method


def make_E(tran_pair):
    def E(q_set):
        """ 空列でのみ遷移可能な状態に遷移する遷移関数 """
        q_list = list()
        for q in q_set:
            q_list += [
                states if q_key[0] == q and q_key[1] == "" else set()
                for q_key, states in tran_pair.items()
            ]

        # もし、空列で遷移できたのなら、もう一度呼び出す
        # その遷移先でも、空列で遷移できる可能性もあるため
        result = reduce(set.union, q_list + [q_set])
        if q_set == result:
            return result
        else:
            return E(result)

    return E

regular_operation.py

"""
正規演算
"""

from nfa import NFA
from state_manager import gen_states


def union_nfa(nfa1: NFA, nfa2: NFA) -> NFA:
    """ 2つのNFA を和集合演算した新しい NFA を構築し、返す """

    start_state = gen_states()
    states = {start_state}.union(nfa1.states).union(nfa2.states)

    # epsilon でそれぞれの開始状態に遷移
    transition_pair = {
        (start_state, ""): {nfa1.start_state, nfa2.start_state},
    }
    transition_pair.update(nfa1.transition_pair)
    transition_pair.update(nfa2.transition_pair)

    # 新しい NFA を生成し、返す
    return NFA(
        states=states,
        alphabets=nfa1.alphabets.union(nfa2.alphabets),
        start_state=start_state,
        accept_states=nfa1.accept_states.union(nfa2.accept_states),
        transition_pair=transition_pair,
    )


def concat_nfa(nfa1: NFA, nfa2: NFA) -> NFA:
    """ 2つのNFA を連結演算した新しい NFA を構築し、返す """

    states = nfa1.states.union(nfa2.states)

    # 受理状態から空列で遷移するものに対して、N2 の開始状態への遷移を追加
    tran_pair = nfa1.transition_pair
    # N1 の受理状態の集合でループ
    for accept_state in nfa1.accept_states:
        # N1 の受理状態から空列で遷移できる状態の集合
        states = tran_pair.get((accept_state, ""), set())
        # 遷移先に N2 の開始状態を追加
        states = states.union({nfa2.start_state})
        tran_pair[(accept_state, "")] = states
    tran_pair.update(nfa2.transition_pair)

    return NFA(
        states=states,
        alphabets=nfa1.alphabets.union(nfa2.alphabets),
        start_state=nfa1.start_state,
        accept_states=nfa2.accept_states,
        transition_pair=tran_pair,
    )


def star_nfa(nfa1: NFA) -> NFA:
    """ 1つのNFA のスター演算をした新しい NFA を構築して返す
    """
    start_state = gen_states()
    states = {start_state}.union(nfa1.states)

    # 新しい開始状態から、空列でN1の開始状態に遷移
    tran_pair = {(start_state, ""): {nfa1.start_state}}
    tran_pair.update(nfa1.transition_pair)
    # 受理状態から、開始状態に空列での遷移 を追加
    for accept_state in nfa1.accept_states:
        # N1 の受理状態から空列で遷移できる状態の集合
        states = tran_pair.get((accept_state, ""), set())
        # 遷移先に N1 の開始状態を追加
        states = states.union({nfa1.start_state})
        tran_pair[(accept_state, "")] = states

    return NFA(
        states=states,
        alphabets=nfa1.alphabets,
        start_state=start_state,
        accept_states={start_state}.union(nfa1.accept_states),
        transition_pair=tran_pair,
    )

sandbox.py

import string
from enum import Enum, auto

from nfa import NFA
from regular_operation import concat_nfa, star_nfa, union_nfa
from graphviz import generate_dot

# アルファベット全部 (記号も)
ALPHABETS = {c for c in string.printable}


def run(nfa, input_str):
    print(nfa.run(input_str), f"\t{input_str}")


def add_all_alphabets_tran(alphabets, tran_pair, from_state, to_state):
    """
    すべてのアルファベットの文字の遷移を追加する
    """
    for a in alphabets:
        states = tran_pair.get((from_state, a), set())
        states = states.union({to_state})
        tran_pair[(from_state, a)] = states
    return tran_pair


# (ab|bc)* という文字列の集合を受理するNFAを構築してみたい
# NFA11 :


"""
NFA1:
    ab
"""


class StatesQ1(Enum):
    q1 = auto()
    q2 = auto()
    q3 = auto()


# 遷移のペア
# 状態が q のときに、a を読みだしたときの遷移先を表す
transition_pair = {
    (StatesQ1.q1, "a"): {StatesQ1.q2},
    (StatesQ1.q2, "b"): {StatesQ1.q3},
}


nfa1 = NFA(
    states=set(StatesQ1),
    alphabets=ALPHABETS,
    start_state=StatesQ1.q1,
    accept_states={StatesQ1.q3},
    transition_pair=transition_pair,
)

print()
print("NFA1")
run(nfa1, "ab")
run(nfa1, "abc")
run(nfa1, "cab")


"""
NFA2:
    bc
"""


class StatesQ2(Enum):
    q1 = auto()
    q2 = auto()
    q3 = auto()


# 遷移のペア
# 状態が q のときに、a を読みだしたときの遷移先を表す
transition_pair2 = {
    (StatesQ2.q1, "b"): {StatesQ2.q2},
    (StatesQ2.q2, "c"): {StatesQ2.q3},
}


nfa2 = NFA(
    states=set(StatesQ2),
    alphabets=ALPHABETS,
    start_state=StatesQ2.q1,
    accept_states={StatesQ2.q3},
    transition_pair=transition_pair2,
)

print()
print("NFA2")
run(nfa2, "bc")
run(nfa2, "bcd")
run(nfa2, "dbc")


"""
NFA3:
    (ab|bc)
"""
nfa3 = union_nfa(nfa1, nfa2)


print()
# print(generate_dot(nfa3))

print()
print("NFA3")
run(nfa3, "bc")
run(nfa3, "ab")
run(nfa3, "abbc")


"""
NFA4:
    (ab|bc)*
"""
nfa4 = star_nfa(nfa3)


print()
print("NFA4")
run(nfa4, "bc")
run(nfa4, "ab")
run(nfa4, "abbc")
run(nfa4, "abbd")
run(nfa4, "")


print()
print(generate_dot(nfa4))

state_manager.py

"""
状態を管理するためのモジュール
sm.gen_states()
"""


state_id = 0


def gen_states() -> int:
    """ 新しいID を生成して返す """
    global state_id
    state_id += 1
    return state_id