/
nfa.py
154 lines (131 loc) · 5.06 KB
/
nfa.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
# -*- coding: utf-8 -*-
"""
NFA definition
----------------------------------------
Author: hiratara <hira.tara@gmail.com>
"""
class NFARuntime(object):
def __init__(self, NFA, debug=False):
self.NFA = NFA
self.cur_states = self.NFA.epsilon_expand(
frozenset([ self.NFA.start ])
)
def do_transition(self, char):
next_states = set()
for state in self.cur_states:
next_states |= self.NFA.transition(state, char)
next_states = self.NFA.epsilon_expand(next_states)
self.cur_states = next_states
def is_accept_state(self):
for state in self.cur_states:
if state in self.NFA.accepts: return True
return False
def does_accept(self, input):
for alphabet in input:
self.do_transition(alphabet)
return self.is_accept_state()
class NFABacktrackRuntime(object):
def __init__(self, NFA, debug=False):
self.NFA = NFA
self.cur_state = self.NFA.start
self.left = None
self.branches = set()
self.done = set()
self.debug = debug
def do_transition(self):
# 文字列を読み終わったので、Falseを返す
if self.left is None:
return False
original_left = self.left
# とりうる遷移
branches = set()
# εを読む
for state in self.NFA.transition(self.cur_state, u""):
branches.add( (state, self.left) )
if self.left:
# まだ読める字があるので、次の1文字を読む
char, self.left = self.left[0], self.left[1:]
for state in self.NFA.transition(self.cur_state, char):
branches.add( (state, self.left) )
else:
# 読める字がないので、読まずに終わる
branches.add( (self.cur_state, None) );
# すでに辿った道を除く
branches = set( filter(lambda x: x not in self.done, branches) )
if branches:
# どの選択肢をとるか選ぶ
self.cur_state, self.left = self._select(branches)
# 残りはバックトラックできるように溜める
self.branches |= branches
if self.debug and self.left is not None:
if original_left == self.left:
char = "''"
else:
char = "'%s'" % original_left[0]
print "-%s->%s" % (char, self.cur_state),
else:
# 遷移がもうない。状態をNoneにしておく
self.cur_state, self.left = None, None
return True
def _select(self, branches):
selected = branches.pop()
self.done.add(selected)
return selected
def backtrack(self):
if self.branches:
self.cur_state, self.left = self._select(self.branches)
if self.debug:
print
print "backtracked: status=%s, left=%s" \
% (self.cur_state, self.left)
return True
else:
return False
def is_accept_state(self):
return self.cur_state in self.NFA.accepts
def does_accept(self, input):
self.left = input
while True:
# 適当な経路でNFAを辿る
while self.do_transition():
pass
if self.is_accept_state():
# 受理状態についたので、受理。
return True
else:
if self.debug: print "[failed!]",
if self.backtrack():
# ダメだったのでバックトラックして別の経路へ
continue
else:
# バックトラックできない。受理しない。
return False
class NondeterministicFiniteAutomaton(object):
def __init__(self,
transition , # a transition function
start , # a start state
accepts , # a set of accept states
):
self.transition = transition
self.start = start
self.accepts = accepts
def get_runtime(self, debug=False):
# return NFARuntime(self, debug)
return NFABacktrackRuntime(self, debug)
def epsilon_expand(self, set_):
# 空文字を辿るべき状態を集めたキュー
que = set( set_ )
# 辿り終わった状態
done = set()
while que:
# キューから取り出す
stat = que.pop()
# 空文字によって辿れる遷移を辿る
nexts = self.transition(stat, "")
# この状態は辿り終わったので、保存
done.add(stat)
# 辿って出て来た状態を、さらに空文字で辿るのに、キューに居れる
for next_stat in nexts:
# 辿り終わってない要素だけ
if not next_stat in done: que.add(next_stat)
return frozenset( done )