0 が 2の倍数か3の倍数の個数なら受理する NFA

nfa.py

"""
0 が 2の倍数か3の倍数の個数なら受理する NFA
"""
from enum import Enum, auto
from functools import reduce


class NFA:
    def __init__(self, states, alphabets, transition, start_state, accept_state, E):
        # self.states = states
        # self.alphabets = alphabets
        self.transition = transition
        self.start_state = start_state
        self.accept_state = accept_state
        # 空列での遷移関数 (開始状態にも使いたいため、こうした)
        self.E = E

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

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

        # 受理状態が含まれていた場合、True
        return not self.accept_state.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()
            ]
        return reduce(set.union, q_list + [q_set])
    return E


class States(Enum):
    q1 = auto()
    q2 = auto()
    q3 = auto()
    q4 = auto()
    q5 = auto()
    q6 = auto()


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


nfa = NFA(
    states={States.q1, States.q2, States.q3, States.q4, States.q5},
    alphabets={"0"},
    transition=make_transition(transition_pair),
    start_state=States.q1,
    accept_state={States.q2, States.q4},
    E=make_E(transition_pair),
)


print(nfa.run("00"))  # False
print(nfa.run("000"))  # False
print(nfa.run("0000"))  # False
print(nfa.run("00000"))  # False