読者です 読者をやめる 読者になる 読者になる

yukiのブログ

作ったものなど

オートマトンをpythonで書く(続き)

この前作ったDFAをいくらか拡張したのでまとめます。ソースはgithubに。

NFA

講義ではDFAの次に非決定性有限オートマトン(Nondeterministic Finite Automata, NFA)が出てきたので、最初の拡張としてNFAを作りました。

NFAは文字列を読み込んでいる途中に状態を複数取ることができます。状態を複数取っているときに文字を読んだ場合、次の状態は現在の各状態の遷移先の和集合です。また文字列を認識するかどうかは最後まで文字を読み込んだあとの状態に終状態が一つでもあるかどうかで判断します。

こう書くと難しく感じますが、DFAのプログラムと骨格はほとんど同じなので特に迷わずに書くことができました。

class NondeterministicFiniteAutomata(Automata):
    """ 非決定性有限オートマトン """

    def run(self, string):
        """ stringを認識するかチェックする """
        states = {self.init_state}
        for char in string:
            if char not in self.alphabets:
                print("ERROR : invalid character \"%s\"" % char)
                return False
            else:
                states = self.next_states(states, char)
        return len(states.intersection(self.final_states)) != 0

    def next_states(self, states, char):
        """ statesからcharを読んだ時の次の状態集合を返す """
        next_states = set()
        for state in states:
            next_states = next_states.union(self.transitions[state].get(char, frozenset()))
        return frozenset(next_states)

参考までに、前の記事で書いたDFAのrun関数も載せておきます。NFAのrun関数と同じような形をしているのが分かるはずです。

class DeterministicFiniteAutomata(Automata):
    """ 決定性有限オートマトン """

    def run(self, string):
        """ stringを認識するかチェックする """
        state = self.init_state
        for char in string:
            if char not in self.alphabets:
                print("ERROR : invalid character \"%s\"" % char)
                return False
            else:
                state = self.transitions[state][char]
        return state in self.final_states

具体的なDFAは次のように作ります。

from Automata import NondeterministicFiniteAutomata as NFA
# 010を部分列に持つ文字列を認識するNFA
a, b, c, d = range(4)
states = {a, b, c, d}
alphabets = {"0", "1"}
transitions = {
    a: {"0": {a, b}, "1": {a}},
    b: {"1": {c}},
    c: {"0": {d}},
    d: {"0": {d}, "1": {d}},
}
init_state = a
final_states = {d}
has_010 = NFA(states, alphabets, transitions, init_state, final_states)

作った上でrun()すれば動作を確認できます。

# pythonコンソール
>>> has_010.run("0001011")
True
>>> has_010.run("0011")
False
>>> has_010.run("001100")
False
>>> has_010.run("100")
False
>>> has_010.run("0100")
True

NFAからDFAへの変換

任意のNFAを等価なDFAに変換するアルゴリズムがあるのでそれも作りました。状態の冪集合を考えることで、NFAが文字を読む間に取りうる状態の集合をDFAの一つの状態としてしまうことがこのアルゴリズムのポイントです。

下のコードでは目標となるDFAのstates, alphabets, transitions, init_state, final_statesを作ることでDFAを作っています。これらの中でalphabetsとinit_stateは自明であり、final_statesはstatesがわかってしまえばすぐに分かるので、作るときに苦労するのはstatesとtransitionsです。

    def convert_to_DFA(self):
        """ 等価なDFAに変換する """
        # 状態と遷移関数を作る
        states = {frozenset({self.init_state})}
        transitions = {}
        to_search = {frozenset({self.init_state})}
        searched = set()
        while len(to_search) != 0:
            searching = to_search.pop()
            searched.add(searching)
            for char in self.alphabets:
                # 実際に遷移させて考える
                reachables = self.next_states(searching, char)
                # 遷移先の状態集合そのものが一つの状態となる
                states.add(reachables)
                if reachables not in searched:
                    # 遷移させた先がまだ調べていない状態だったらさらに調べる必要がある
                    to_search.add(reachables)
                if not transitions.get(searching):
                    # 二重辞書の要素を一気に作ることはできないので注意
                    transitions[searching] = {}
                # 遷移を追加する
                transitions[searching][char] = frozenset(reachables)

        # DFAの終状態は終状態を一つでも含む状態全体からなる集合
        final_states = set([x for x in states if len(self.final_states.intersection(x)) != 0])
        # DFAの始状態はNFAの始状態だけからなる集合
        init_state = frozenset({self.init_state})
        # DFAのアルファベットはNFAと同じ
        alphabets = self.alphabets
        return DeterministicFiniteAutomata(states, alphabets, transitions, init_state, final_states)

次のように使います。同じ機能を持つDFAができていますが、変換によって状態数が増え、複雑になっていることがわかります。

# has_010を作った状態のpythonコンソール
>>> print(has_010)

Automata
    states      : {0, 1, 2, 3}
    alphabets   : {'1', '0'}
    transitions : 0 : {'1': {0}, '0': {0, 1}}
                  1 : {'1': {2}}
                  2 : {'0': {3}}
                  3 : {'1': {3}, '0': {3}}
    init_state  : 0
    final_states: {3}
>>> has_010_DFA = has_010.convert_to_DFA()
>>> print(has_010_DFA)
Automata
    states      : {{0, 2, 3}, {0, 2}, {0, 1, 3}, {0}, {0, 3}, {0, 1}}
    alphabets   : {'1', '0'}
    transitions : {0, 2, 3} : {'1': {0, 3}, '0': {0, 1, 3}}
                  {0, 2} : {'1': {0}, '0': {0, 1, 3}}
                  {0} : {'1': {0}, '0': {0, 1}}
                  {0, 1, 3} : {'1': {0, 2, 3}, '0': {0, 1, 3}}
                  {0, 3} : {'1': {0, 3}, '0': {0, 1, 3}}
                  {0, 1} : {'1': {0, 2}, '0': {0, 1}}
    init_state  : {0}
    final_states: {{0, 2, 3}, {0, 3}, {0, 1, 3}}

>>> has_010_DFA.run("010")
True
>>> has_010_DFA.run("0110")
False
>>> has_010_DFA.run("100110")
False
>>> has_010_DFA.run("1001010")
True

全てのNFAはDFAに変換できることと全てのDFAはNFAなことから、DFAとNFAが同じ計算能力を持つことがわかります。

εNFA

NFAをさらに拡張してイプシロン動作付き非決定性有限オートマトン(εNFA)も作りました。

εNFAとNFAの違いは、イプシロン遷移があるかどうかです。イプシロン遷移が状態\(p\)から状態\(q\)に張られていた場合、状態\(p\)に到達したら無条件で状態\(q\)にも到達したとみなします。さらに状態\(q\)から別の状態にイプシロン遷移が張られていれば、その状態についても同様です。

違いがこれだけなのでNFAをεNFAにするのは簡単かと思いましたがそれなりに手こずりました。イプシロン遷移を一回たどるだけでは不十分で、飽和するまでたどりきらないといけないためです。

class NFAWithEpsilonTransition(Automata):
    """ ε動作付き非決定性有限オートマトン """

    def reachables_with_a_epsilon_from(self, state):
        """ stateから一回のε遷移だけで到達可能な状態の集合を返す """
        return frozenset(self.transitions[state].get(-1, {}))

    def reachables_with_epsilons_from(self, state):
        """ stateからε遷移だけで到達可能な状態の集合を返す """
        ans = frozenset([state])
        reachables = self.reachables_with_a_epsilon_from(state)
        while not reachables.issubset(ans): # 飽和するまで繰り返す
            ans = ans.union(reachables)
            new_reachables = frozenset()
            for reachable in reachables:
                new_reachables = new_reachables.union(self.reachables_with_a_epsilon_from(reachable))
            reachables = new_reachables
        return ans

    def next_states(self, states, char):
        """ statesからcharを読んだ時の次の状態集合を返す """
        next_states = frozenset()
        for state in states:
            for reachable in self.transitions[state].get(char, frozenset()):
                next_states = next_states.union(self.reachables_with_epsilons_from(reachable))
        return frozenset(next_states)

    def run(self, string):
        """ stringを認識するかチェックする """
        states = self.reachables_with_epsilons_from(self.init_state)
        for char in string:
            if char not in self.alphabets:
                print("ERROR : invalid character \"%s\"" % char)
                return False
            else:
                states = self.next_states(states, char)
        return len(states.intersection(self.final_states)) != 0

以下のようにして動かします。

>>> from Automata import NFAWithEpsilonTransition as eNFA
>>> a, b, c, d, e = range(5)
>>> states = {a, b, c, d, e}
>>> alphabets = {"0", "1", "2", "3", "4"}
>>> transitions = {
...     a: {"0": {a}, -1: {b}},
...     b: {"1": {b}, -1: {c}},
...     c: {"2": {c}, -1: {d}},
...     d: {"3": {d}, -1: {e}},
...     e: {"4": {e}}
>>> }
>>> init_state = a
>>> final_states = {e}
>>> is_increasing = eNFA(states, alphabets, transitions, init_state, final_states)

>>> is_increasing.run("01144")
True
>>> is_increasing.run("01231")
False
>>> is_increasing.run("00004")
True
>>> is_increasing.run("33444")
True

NFAと同様の方法でεNFAもDFAに変換することができます(コードはほとんど同じなので省略します)。

DFAの最小化

任意のDFAは最小化することができます。つまり、任意のDFAに対して、そのDFAが同じ言語を認識するDFAのうち状態数が最小のDFAを作ることができます。

重要となるのは以下の区別できないという関係です。

DFA \(M(Q,\varSigma,\delta,q_0,F)\) について、状態 \(p,q \in Q\)区別できない

\(\Longleftrightarrow\) 全ての文字列\(s \in \varSigma^\ast\)について\(\delta^\ast (p,s) \in F \Leftrightarrow \delta^\ast (p,s) \in F\)

DFAの2つの状態が区別できないとことを言い換えると、2つの状態がDFAの中で同じ役割をしていると言う事ができます。DFAがどちらの状態にあってもそれから読む文字列に対して全く同じ反応を示すからです。「区別できない」という名前もここからきたのでしょう。

あるいは、区別できない2つの状態はDFAの中で無駄な状態だともいえます。なぜなら、区別できない状態の遷移を上手くいじれば2つの状態を1つにまとめてしまえることを示せる定理があるからです。いわゆるMyhill-Nerodeの定理(の一部)です。

DFA \(M(Q,\varSigma,\delta,q_0,F)\)が最小DFAである。

\(\Longleftrightarrow\) 任意の異なる状態の組\((p,q) \in Q \times Q (p \neq q)\)が区別できる。

すごくざっくり言うと、「最小DFAには"無駄な"状態が存在しない / ”無駄な”状態が無いDFAは最小」ということになります。

この定理の証明は区別できないという関係の同値類を使って遷移の具体的な張り方を示すことで行います。ここでは省略します。

というわけでDFAを最小化するには、状態のうち区別できるペアを見つけ、そのペアを一つの状態として良い感じに遷移を張ればよいということになります。以下の性質を使います。どちらも定義から明らかです。

  • \(p \in F\)\(q \notin F\)について、\(p\)\(q\)は区別できる。
  • \((p, q) \in Q \times Q\)について、ある\(c \in \varSigma\)について\(\delta(p, c)\)\(\delta(q, c)\)が区別できるならば、\(p\)\(q\)も区別できる。

これをプログラムにすると以下のようになります。

class DeterministicFiniteAutomata(Automata):
    """ 決定性有限オートマトン """
    ...
    (略)
    ...
    def minimized(self):
        """ 最小化されたDFAを返す """

        # markedとunmarkedを初期化
        # markedは区別できるペアの集合
        # unmarkedは区別できないペアの集合
        marked = set()
        unmarked = set()
        checked = set()
        for p in self.states:
            for q in self.states:
                if frozenset({p, q}) in checked or p == q:
                    continue
                if (p in self.final_states and q not in self.final_states) or \
                        (q in self.final_states and p not in self.final_states):
                    marked.add(frozenset({p, q}))
                else:
                    unmarked.add(frozenset({p, q}))
                checked.add(frozenset({p, q}))
                checked.add(frozenset({q, p}))

        # markedを限界まで増やす
        flag = True
        while flag:
            flag = False
            for p, q in unmarked:
                for s in self.alphabets:
                    # (p,q)をsで遷移させてmarkedにはいるなら(p,q)もmarkedに入る
                    if frozenset({self.transitions[p][s], self.transitions[q][s]}) in marked:
                        flag = True
                        marked.add(frozenset({p, q}))
                        unmarked.remove(frozenset({p, q}))
                        break
                if flag:
                    break

        # まず最小DFAの状態がどうなるか計算する
        states_dict = {}
        for p in self.states:
            states_dict[p] = {p}
        for p in self.states:
            for q in self.states:
                if frozenset({p, q}) in unmarked:
                    states_dict[p].add(q)
                    states_dict[q].add(p)

        # 次にstates_dictからtransitions, init_state, final_statesを作る
        states = set()
        init_state = None
        final_states = set()
        transitions = {}
        for p in self.states:
            state = frozenset(states_dict[p])
            if state in states:
                continue
            states.add(state)
            transitions[state] = {}
            for s in self.alphabets:
                # next(iter(X))は「Xから適当に一つ取る」という意味
                transitions[state][s] = states_dict[self.transitions[next(iter(state))][s]]
            if self.init_state in state:
                init_state = state
            if len(self.final_states.intersection(state)) != 0:
                final_states.add(state)
        alphabets = self.alphabets
        return DeterministicFiniteAutomata(states, alphabets, transitions, init_state, final_states)

以下のように使います。たしかに状態数が減っているのがわかります。

>>> from Automata import DeterministicFiniteAutomata as DFA
>>> a, b, c, d, e, f, g, h, = range(8)
>>> states = {a, b, c, d, e, f, g, h}
>>> alphabets = {"0", "1"}
>>> transitions = {
...     a: {"0": b, "1": f},
...     b: {"0": g, "1": c},
...     c: {"0": a, "1": c},
...     d: {"0": c, "1": g},
...     e: {"0": h, "1": f},
...     f: {"0": c, "1": g},
...     g: {"0": g, "1": e},
...     h: {"0": g, "1": c}
... }
>>> init_state = a
>>> final_states = {c}
>>> automata = DFA(states, alphabets, transitions, init_state, final_states)
>>> print(automata)

Automata
    states      : {0, 1, 2, 3, 4, 5, 6, 7}
    alphabets   : {'1', '0'}
    transitions : 0 : {'1': 5, '0': 1}
                  1 : {'1': 2, '0': 6}
                  2 : {'1': 2, '0': 0}
                  3 : {'1': 6, '0': 2}
                  4 : {'1': 5, '0': 7}
                  5 : {'1': 6, '0': 2}
                  6 : {'1': 4, '0': 6}
                  7 : {'1': 2, '0': 6}
    init_state  : 0
    final_states: {2}

>>> minimized = automata.minimized()
>>> print(minimized)

Automata
    states      : {{2}, {6}, {0, 4}, {1, 7}, {3, 5}}
    alphabets   : {'1', '0'}
    transitions : {6} : {'1': {0, 4}, '0': {6}}
                  {2} : {'1': {2}, '0': {0, 4}}
                  {0, 4} : {'1': {3, 5}, '0': {1, 7}}
                  {3, 5} : {'1': {6}, '0': {2}}
                  {1, 7} : {'1': {2}, '0': {6}}
    init_state  : {0, 4}
    final_states: {{2}}

感想

正規表現やりたいんだけどできるかな...