Pythonでオートマトンを作って正規表現を試してみた

非決定性有限オートマトンというものを勉強してみたのでPythonで実装し、正規表現のパターンマッチャ―も作りました。

実装

複数の集合の和集合を求める関数
まずは周辺の関数を作っておきます。引数にコレクションを複数指定して使います。

def sum_of_sets(set_list):
 res = set()
 for set_instance in set_list:
   for element in set_instance:
     res.add(element)
 return res

#動作例
print(sum_of_sets([[1,3],[3,5],[1,6,7]]))

{1, 3, 5, 6, 7}

非決定性有限オートマトン
ここでの s0, self.s, T[state_element][x] は複数の状態をまとめたコレクション型であることに注意。

class NFA:
 def __init__(self,s0,T:dict,A):
   '''
   s0 : 初期の状態の集合
   T : T[state_element][x] state_elementの際にxを受け取った後の状態の集合
   A : 受け入れる状態の集合
   '''
   self.s = s0
   self.T = T
   self.A = A
 def takein(self,x):
   self.s = sum_of_sets([T[state_element][x] for state_element in self.s])
   return self.__str__()
 def is_acceptable(self):
   for state_element in self.s:
     if state_element in self.A:
       return True
   return False
 def __str__(self):
   return ','.join([str(x)for x in self.s])

NFAインスタンスに続けて入力を行う関数
便利のため、もう一つ周辺の関数を作っておきます。

def takein_multiple(nfa,xs):
 for x in xs:
   nfa.takein(x)
 return nfa

(a|ab)*cにマッチするか調べるNFA

遷移はこういう感じにします。

初期状態は1なので

s0 = [1]

許容される状態は3なので

A = [3]

そして遷移関数は

T = {
   1:{'a':[1,2],'b':[],'c':[3]},
  2:{'a':[],'b':[1],'c':[]},
  3:{'a':[],'b':[],'c':[]}
}

と表せます。遷移する先がない場合は空集合にしておきます。

そしてこのようにインスタンスを作ります。

nfa = NFA(s0,T,A)

入力に対する状態の遷移を入力の都度見ていくと

print(nfa.takein('a'))
print(nfa.takein('a'))
print(nfa.takein('b'))
print(nfa.takein('c'))

1,2
1,2
1
3

パターンマッチした入力が得られて初めて状態3に行っている様子がよく分かりました。

色々やってみます。

assert takein_multiple(NFA(s0,T,A),'aaaaaac').is_acceptable()
assert takein_multiple(NFA(s0,T,A),'ababababc').is_acceptable()
assert takein_multiple(NFA(s0,T,A),'aabc').is_acceptable()
assert not takein_multiple(NFA(s0,T,A),'abbac').is_acceptable()
assert not takein_multiple(NFA(s0,T,A),'abaaa').is_acceptable()