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

$ py -3 sandbox.py

NFA1
True    ab
False   abc
False   cab

NFA2
True    bc
False   bcd
False   dbc


NFA3
True    bc
True    ab
False   abbc

NFA4
True    bc
True    ab
True    abbc
False   abbd
True

digraph sample {
        node [ shape = circle ];
        q0 [ shape = point ];
        q0 -> q2;
        q2 -> q1 [label = "ε"];
        q1 -> Q2_q1 [label = "ε"];
        q1 -> Q1_q1 [label = "ε"];
        Q1_q1 -> Q1_q2 [label = "a"];
        Q1_q2 -> Q1_q3 [label = "b"];
        Q2_q1 -> Q2_q2 [label = "b"];
        Q2_q2 -> Q2_q3 [label = "c"];
        Q1_q3 -> q1 [label = "ε"];
        Q2_q3 -> q1 [label = "ε"];
        Q1_q3 [ shape = doublecircle ];
        q2 [ shape = doublecircle ];
        Q2_q3 [ shape = doublecircle ];
}