DFA の最小化 (minimum_states.py で最小化する関数を定義した)

dfa.py

"""
0 を偶数個含む文字列の言語を受理する DFA
"""
from enum import Enum, auto


class DFA:
    def __init__(self, states, alphabets, transition_pair, start_state, accept_states):
        self.states = states
        self.alphabets = alphabets
        self.transition_pair = transition_pair
        self.transition = make_transition(transition_pair)
        self.start_state = start_state
        self.accept_states = accept_states

        self.cur_state = start_state

    def run(self, input_str: str) -> bool:
        """ 入力文字列を読み出し、受理するかどうかを返す
        """
        for s in input_str:
            self.cur_state = self.transition(self.cur_state, s)
        return self.cur_state in self.accept_states


class States(Enum):
    q1 = auto()
    q2 = auto()


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

    def transition_method(q, a):
        return tran.get((q, a))

    return transition_method


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


dfa = DFA(
    states={States.q1, States.q2},
    alphabets={"0", "1"},
    transition_pair=transition_pair,
    start_state=States.q1,
    accept_states={States.q1},
)


assert dfa.run("0101") is True
assert dfa.run("01010") is False
assert dfa.run("11010") is False

graphviz.py

import re
from nfa import NFA
from dfa import DFA
from typing import Union, Dict


def tweak_q(q):
    s = re.sub(r"(\.|\(|\)|\s+|{|}|:|<|>|,)", "_", str(q))
    if "States" in s:
        return s.replace("States", "")
    else:
        return f"q{q}"


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

    from_to_labels: Dict = {}
    for tran, states in fa.transition_pair.items():
        if type(fa) == DFA:
            # DFA なら、states が1つのもの
            states = list([states])

        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 fa.accept_states:
        result += f"""\t{tweak_q(q)} [ shape = doublecircle ];\n"""
    result += "}"
    return result

minimum_states.py

"""
DFA の最小化
"""

from typing import FrozenSet, List, Set, Dict

from dfa import DFA
from states_equivalent_better import equivalent_pair_set_better


def make_blocks(states: Set, equivalent_pair_set: Set[FrozenSet]) -> Set[FrozenSet]:
    """ ブロックを構築する

    :param states:
        すべての状態の集合
    :param equivalent_pair_set:
        同値な状態のペアの集合
    """
    equivalent_pairs = list(equivalent_pair_set)

    blocks: List[FrozenSet] = list()

    while len(equivalent_pairs) != 0:
        pair = equivalent_pairs.pop(0)
        p, q = list(pair)
        states = states - pair

        # 追加したか
        replace_block = None
        replace_idx = -1

        # 構築されているブロックにいれば、そこに追加
        for i, block in enumerate(blocks):
            if p in block or q in block:
                replace_block = frozenset(list(block) + [p, q])
                replace_idx = i
                break

        if replace_block is None:
            # 追加されなければ、新しいブロックを追加
            blocks.append(frozenset([p, q]))
        else:
            # 追加されていれば、そのブロックを置き換える
            blocks[replace_idx : replace_idx + 1] = [replace_block]

    # すべての状態と区別可能な状態はそのまま足す
    blocks += [frozenset([s]) for s in states]

    return set(blocks)


# assert make_blocks(
#     {"A", "B", "C", "D"}, {frozenset({"A", "C"}), frozenset({"B", "D"})},
# ) == {frozenset({"A", "C"}), frozenset({"B", "D"})}
#
# assert make_blocks(
#     {"A", "B", "C", "D", "E"},
#     {
#         frozenset({"A", "C"}),
#         frozenset({"A", "D"}),
#         frozenset({"C", "D"}),
#         frozenset({"B", "E"}),
#     },
# ) == {frozenset({"A", "C", "D"}), frozenset({"B", "E"})}
#
#
# assert make_blocks(
#     {"A", "B", "C", "D", "E", "F", "G", "H"},
#     {frozenset({"A", "E"}), frozenset({"B", "H"}), frozenset({"D", "F"})},
# ) == {
#     frozenset({"A", "E"}),
#     frozenset({"C"}),
#     frozenset({"B", "H"}),
#     frozenset({"D", "F"}),
#     frozenset({"G"}),
# }


def make_minimum_dfa(dfa: DFA):
    """make_minimum_dfa.

    :param dfa:
    :type dfa: DFA
        最小化するのDFA
    """
    eq_pair_set: Set[FrozenSet] = equivalent_pair_set_better(dfa)
    blocks: Set[FrozenSet] = make_blocks(dfa.states, eq_pair_set)

    # 開始状態: 開始状態が属すブロック
    start_state = [block for block in blocks if dfa.start_state in block][0]
    # 受理状態: 受理状態の状態が属すブロックの集合
    accept_states = set(
        block for block in blocks if not block.isdisjoint(dfa.accept_states)
    )
    # 遷移関数
    transition_pair: Dict = dict()
    for block in blocks:
        for a in dfa.alphabets:
            # 適当に選ぶ
            q = list(block)[0]
            p = dfa.transition(q, a)
            # p を含むブロックを取得
            to_block = [block for block in blocks if p in block][0]
            transition_pair[(block, a)] = to_block

    return DFA(
        states=blocks,
        alphabets=dfa.alphabets,
        transition_pair=transition_pair,
        start_state=start_state,
        accept_states=accept_states,
    )

nfa.py

"""
NFA
"""
from functools import reduce
from typing import Set


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

        # 和集合演算するときに使うため、ここで関数を生成するようにしてみた
        # TODO: 空列の遷移を取り除いたあとの状態遷移のdictを生成しておきたい
        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 = 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

sandbox.py

from enum import Enum, auto

from dfa import DFA
from graphviz import generate_dot
from minimum_states import make_minimum_dfa


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


class StatesQ1(Enum):
    qA = auto()
    qB = auto()
    qC = auto()
    qD = auto()
    qE = auto()
    qF = auto()
    qG = auto()
    qH = auto()


# 遷移のペア
# 状態が q のときに、a を読みだしたときの遷移先を表す
transition_pair = {
    (StatesQ1.qA, "0"): StatesQ1.qB,
    (StatesQ1.qA, "1"): StatesQ1.qF,
    (StatesQ1.qB, "0"): StatesQ1.qG,
    (StatesQ1.qB, "1"): StatesQ1.qC,
    (StatesQ1.qC, "0"): StatesQ1.qA,
    (StatesQ1.qC, "1"): StatesQ1.qC,
    (StatesQ1.qD, "0"): StatesQ1.qC,
    (StatesQ1.qD, "1"): StatesQ1.qG,
    (StatesQ1.qE, "0"): StatesQ1.qH,
    (StatesQ1.qE, "1"): StatesQ1.qF,
    (StatesQ1.qF, "0"): StatesQ1.qC,
    (StatesQ1.qF, "1"): StatesQ1.qG,
    (StatesQ1.qG, "0"): StatesQ1.qG,
    (StatesQ1.qG, "1"): StatesQ1.qE,
    (StatesQ1.qH, "0"): StatesQ1.qG,
    (StatesQ1.qH, "1"): StatesQ1.qC,
}


dfa = DFA(
    states=set(StatesQ1),
    alphabets={"0", "1"},
    transition_pair=transition_pair,
    start_state=StatesQ1.qA,
    accept_states={StatesQ1.qC},
)

run(dfa, "01")
run(dfa, "110101")
run(dfa, "0100")
run(dfa, "10101")

print()
print(generate_dot(dfa, label_show=False))
print()

mini_dfa = make_minimum_dfa(dfa)


run(mini_dfa, "01")
run(mini_dfa, "110101")
run(mini_dfa, "0100")
run(mini_dfa, "10101")


print()
print(generate_dot(mini_dfa, label_show=False))

states_equivalent_better.py

"""
DFA の状態の同値性の判定

穴埋めアルゴリズムを使って、計算する
ちょっといい感じ ver
"""

from queue import SimpleQueue
from typing import Dict, FrozenSet, Set, Union, List

from dfa import DFA
from nfa import NFA


def combinations(set_: Set) -> Set[FrozenSet]:
    """ すべての組み合わせの set を生成する """
    result = set()
    for s in set_:
        for t in set_:
            if s != t:
                # 同じものはだめ
                result.add(frozenset({s, t}))
    return result


def combinations_2(set1: Set, set2: Set) -> Set[FrozenSet]:
    """ すべての組み合わせの set を生成する """
    result = set()
    for s in set1:
        for t in set2:
            if s != t:
                # 同じものはだめ
                result.add(frozenset({s, t}))
    return result


def equivalent_pair_set_better(dfa: Union[DFA, NFA]) -> Set[FrozenSet]:
    """ 同値な状態の対の集合を返す
    """
    # すべての状態の対の集合
    pair_set = combinations(dfa.states)

    # チェックする状態のペア
    will_trace_pairs: SimpleQueue[FrozenSet] = SimpleQueue()

    # 最初は受理状態と受理状態以外の状態がチェック対象となる
    for pair in combinations_2(dfa.states, dfa.accept_states):
        will_trace_pairs.put_nowait(pair)

    # 区別可能な状態の対の集合
    # 「それ以外の状態」と「それ以外の状態」は空列で区別可能
    disting_pair_set: Set[FrozenSet] = table_filling_better(
        pair_set, will_trace_pairs, dfa.transition_pair, dfa.alphabets
    )
    # 区別可能なものを取り除いた集合を返す (同値な状態の対の集合を返す)

    return pair_set - disting_pair_set


def table_filling_better(
    pair_set, will_trace_pairs: SimpleQueue, trans_pair, alphabets
) -> Set[FrozenSet]:
    """ 穴埋めアルゴリズム
    区別可能な状態の対を求める

    pair_set:
        すべての状態の対の集合
    will_trace_pairs:
        チェック対象のペアの集合
    trans_pair:
        遷移情報
    alphabets:
        アルファベットの集合
    """
    # 1文字での遷移先の状態の対が区別可能かどうかをチェックし、
    # 区別可能であった場合、その状態の対も区別可能
    # 区別可能ではなかった場合、その状態の対は同値である

    def trans(q, a):
        # DFA のため、必ず遷移が存在するはず
        res = trans_pair.get((q, a))
        if type(res) == set:
            # NFA から DFA に変換した場合、set だから、こうする
            return list(res)[0]
        else:
            return res

    # すべての状態のペアに依存するペアのリストを生成する
    dependence_list_dict: Dict[FrozenSet, List] = dict()

    result: Set[FrozenSet] = set()

    # 依存する状態のペアのリストを生成
    for pair in pair_set:
        p, q = list(pair)
        for a in alphabets:
            r = trans(p, a)
            s = trans(q, a)

            # 状態が同じではない or
            if r != s:
                lst = dependence_list_dict.get(frozenset([r, s]), [])
                lst += [{p, q}]
                dependence_list_dict[frozenset([r, s])] = lst

    # 依存するリストをたどる必要がなくなるまでループ
    while not will_trace_pairs.empty():
        r, s = will_trace_pairs.get_nowait()
        # 依存する状態をチェック
        for pair in dependence_list_dict.get(frozenset([r, s]), []):
            # 区別可能な状態に含まれていなければ、追加
            # また、そのリストもたどるため、キューに追加する
            if pair not in result:
                will_trace_pairs.put_nowait(pair)
                result.add(frozenset(list(pair)))
    return result

両方、同じ文字列を受理した
TODO: 2つの DFA の等価性を調べる関数作る

最小化する前の遷移図

最小化したあとの遷移図