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

yukiのブログ

作ったものなど

オートマトンをpythonで書く

(非)決定性有限オートマトンチューリングマシンより真に弱い計算能力を持つというのはどのオートマトンの教科書にも書いてあることです。このことが意味するのは、オートマトンでできることは全てチューリングマシンでできるということです。ということでチューリングマシンである普通のコンピューターでオートマトンを動かすプログラムをpythonで書きました。3か月間オートマトンについての講義を受け、その期末試験の直後にプログラムを書き始めたので、驚くほど簡単に書けました。

github.com

DFA

まずは一番単純なオートマトン、決定性有限オートマトン(DFA)について書きます。

DFAの形式的定義

教科書をめくると、DFAは以下のように定義してあります。

{
    M=(Q, \Sigma, \delta, q_0, F)
}

ここで記号は以下のような意味を持ちます。

{
  \begin{aligned}
    Q &: 状態の集合 \newline
    \Sigma &: アルファベット\newline
    \delta &: 遷移関数 \ \ \  (\subset Q \times \Sigma \times Q)\newline
    q_0 &: 初期状態 \ \ \ (\in Q) \newline
    F &: 終状態 \ \ \ (\subset Q) \newline
  \end{aligned}
}

オートマトンがこのように定義されているということから、DFAを表現するクラスが保持すべき情報がこれだけだと判断しました。もちろんどうにかして情報を圧縮したり分かりやすいようにまとめ直すことも可能だとは思いましたが、形式的定義が十分わかりやすいと思ったので自分でどうにかするのはやめました。

クラスのコンストラクタは以下のようになります。

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

    def __init__(self, states, alphabets, transitions, init_state, final_states):
        self.states = states
        self.alphabets = alphabets
        self.transitions = transitions
        self.init_state = init_state
        self.final_states = final_states

データ構造

オートマトンを表現する情報のデータ構造について書きます。

{Q} (状態の集合)について

オートマトンの形式的定義では{Q}に関する縛りは何もありません。このことが意味するのは、{Q}の中身が文字列だろうと整数だろうと関数だろうと関係が無く、ただ区別ができて集合に属しているかチェックできるものならば何でもいい、ということです。

プログラムでも同じ方針を取り、{Q}を"任意の要素の集合"として表現しました。pythonはもともと動的型付けなので、{Q}の要素が任意であることを明示する必要はありません。また要素の集合を表現するには組み込みのsetクラスを利用できます。

{Q}のデータ構造が"任意の要素の集合"と決まれば、{q_0}{F}のデータ構造もそれぞれ"任意", “任意の要素の集合"と決まります。

以下に{Q, q_0, F}の一例を示します。ここでは状態を表すのに自然数を使っています。

a, b, c = range(3) # 参照しやすいように変数にしておく
states = {a, b, c} # オートマトンは{a,b,c,d,e}の5つの状態からなる
init_state = a     # オートマトンの初期状態はaである
final_states = {a} # オートマトンの終了状態の集合は{a}である

{\Sigma} (アルファベット)について

これは簡単でした。文字の集合を表せばよいので、{Q}と同じように組み込みのsetクラスを利用しました。

以下に{\Sigma}の例を示します。

alphabets = {"0", "1"} # このオートマトンは"0"と"1"からなる文字列を読む

{\delta} (遷移関数)について

遷移関数の型は {Q \times \Sigma \times Q}なので、二重辞書を使って表現しました。

「遷移関数」という名前からpythonの関数を使って表現してもいいのではないかと思いましたが、そうしてしまうとオートマトンに本来できない計算が遷移関数の中で行われてしまう可能性があったのでやめにしました。

以下に{\delta}の一例を示します。

transitions = {
    a: {"0": a, "1": b}, # 状態aで"0"を読んだらaに、"1"を読んだらbに遷移
    b: {"0": c, "1": a}, # 状態bで"0"を読んだらcに、"1"を読んだらaに遷移
    c: {"0": b, "1": c}, # 状態cで"0"を読んだらbに、"1"を読んだらcに遷移
}

文字列の判定

オートマトンが持つ唯一の機能である、文字列を受け取ってそれを受理するか拒否するかを決める処理について書きます。

文字列を一文字ずつ読み込み、そのたびごとに状態を遷移させ、最後の文字を読んだときの状態が終状態に含まれるか否かで受理するか拒否するかを決めます。データ構造をきちんと決めてしまえばこの処理を書くのは楽でした。

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

    def __init__(self, states, alphabets, transitions, init_state, final_states):
        (略)

    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 -1
            else:
                state = self.transitions[state][char] # 状態を遷移させる
        return state in self.final_states

DFAの例

これでDFAのクラスは完成なので、このクラスを使ったDFAの例を一つ示します。githubのtest.pyから抜き取ってきたものです。

from Automata import DeterministicFiniteAutomata as DFA

""" 二進表記で3の倍数の文字列を認識するDFA """
a, b, c = range(3)
states = {a, b, c}
alphabets = {"0", "1"}
transitions = {
    a: {"0": a, "1": b},
    b: {"0": c, "1": a},
    c: {"0": b, "1": c},
}
init_state = a
final_states = {a}
automata = DFA(states, alphabets, transitions, init_state, final_states)


tests = (("00000", True),       # 0
         ("0011", True),        # 3
         ("01110", False),      # 14
         ("1001", True),        # 9
         ("1110101110", True))  # 942

print("is_divisible_by_3".center(70, "-"))
for string, expected in tests:
    result = automata.run(string)
    print("%s: \"%s\"" % (str(result).ljust(5), string))
    if result != expected:
        print("ERROR")

これを実行すると以下のような出力が得られ、正しく動作していることが確かめられます。

python mod3.py
--------------------------is_divisible_by_3---------------------------
True : "00000"
True : "0011"
False: "01110"
True : "1001"
True : "1110101110"

感想

NFAとeNFAはそのうち…