modulo-DFA

!modulo-DFA-README.md

倍数判定を行う有限オートマトンを作成し、PDF として出力します。動かしてみる場合は main 内の RADIX と MOD を適当に弄ってください。

• 二進法において 3 の倍数か判定するオートマトン（一番上の桁が一文字目になります）

• 十進法において 7 の倍数か判定するオートマトン

modulo-DFA.py

##
# @file modulo-dfa.py
# @brief 基数 RADIX (2 <= RADIX <= 36) と法 MOD に対し、RADIX 進法表記された自然数が MOD の倍数であるかどうか判定する有限オートマトンを作成します。

from numpy import base_repr
from collections import defaultdict
from itertools import combinations_with_replacement
from graphviz import Digraph

##
# @class FiniteStateAutomaton
# @brief 有限オートマトンの実装です。
class FiniteStateAutomaton:
    ##
    # @fn __init__
    # @param states 状態の set。
    # @param alphabet 入力記号の set。
    # @param initial_state 初期状態。states の元でなければなりません。
    # @param final_states 受理状態集合。states の部分集合でなければなりません。
    # @param delta states の元と alphabet の元を受け取り、states の元を返す関数。
    def __init__(self, states, alphabet, initial_state, final_states, delta):
        self.states = states
        self.alphabet = alphabet
        self.initial_state = initial_state
        self.final_states = final_states
        self.delta = delta

    ##
    # @fn reduced
    # @brief Moore reduction procedure の実装です。有限オートマトンの状態数を最小化します。
    # @return 状態数を最小化した有限オートマトン。
    def reduced(self):
        # 等価な状態のソート済みペアの集合
        equive_state_tuples = {
            tuple(sorted((p, q))) for (p, q) in combinations_with_replacement(self.states, 2)
            if (p in self.final_states) == (q in self.final_states)
        }
        while True:
            prev = equive_state_tuples
            equive_state_tuples = {
                (p, q) for (p, q) in equive_state_tuples
                if all(tuple(sorted((self.delta(p, c), self.delta(q, c)))) in equive_state_tuples for c in self.alphabet)
            }
            if (equive_state_tuples == prev):
                break
        # 状態からそれが所属する同値類内の代表への辞書
        representatives = {}
        for (p, q) in sorted(equive_state_tuples):
            representatives[q] = representatives.get(p, p)
        return FiniteStateAutomaton (
            {representatives[state] for state in self.states},
            self.alphabet,
            representatives[self.initial_state],
            {representatives[final_state] for final_state in self.final_states},
            lambda state, c: representatives[self.delta(state, c)]
        )

    ##
    # @fn to_dot
    # @brief 遷移関数のグラフを返却します。
    # @return 遷移関数を表現する graphviz オブジェクト。
    def to_dot(self, filename):
        # 状態 p から状態 q へ移動させる文字のリストの辞書
        transit_char_lists = defaultdict(list)
        for state in self.states:
            for c in self.alphabet:
                transit_char_lists[(state, self.delta(state,c))].append(c)
        # ノード、エッジの登録
        g = Digraph(filename=filename, graph_attr={'rankdir' : 'LR'}, node_attr={'shape' : 'circle'})
        for state in self.states:
            if state in self.final_states:
                g.node(f'state_{state}', label='', shape='doublecircle')
            else:
                g.node(f'state_{state}', label='')
        for (p, q), tcl in transit_char_lists.items():
            g.edge(f'state_{p}', f'state_{q}', label=', '.join(sorted(tcl)))
        # 初期状態を指すエッジの登録
        g.node('_', style='invis', label='', fixedsize='true', width='0')
        g.edge('_', f'state_{self.initial_state}')
        return g

if __name__ == '__main__':
    RADIX = 10
    MOD = 7
    FA = FiniteStateAutomaton (
        set(range(MOD)),
        {base_repr(n, base=RADIX) for n in range(RADIX)},
        0,
        {0},
        lambda state, c: (RADIX * state + int(c, RADIX)) % MOD
    )
    # 状態数を最適化しない場合
    #FA.to_dot('result.dot').render()
    # 最適化する場合
    FA.reduced().to_dot('result.dot').render()