53 lines
1.6 KiB
Python
53 lines
1.6 KiB
Python
import sys
|
|
|
|
class NFA:
|
|
def __init__(self):
|
|
self.initial_state = '0'
|
|
self.final_states = set()
|
|
|
|
self.transitions = dict()
|
|
self.alphabet = set()
|
|
|
|
def add_transition(self, state_from, state_to, symbol):
|
|
|
|
if state_from in self.transitions.keys():
|
|
if symbol not in self.transitions[state_from].keys():
|
|
self.transitions[state_from][symbol] = {state_to}
|
|
else:
|
|
self.transitions[state_from][symbol] |= {state_to}
|
|
else:
|
|
self.transitions[state_from] = dict()
|
|
self.transitions[state_from][symbol] = {state_to}
|
|
|
|
def add_final_state(self, state):
|
|
self.final_states.add(state)
|
|
|
|
def get_final_states(self, string):
|
|
current_states = {self.initial_state}
|
|
for symbol in string:
|
|
current_states = {state for current_state in current_states for state in self.transitions.get(current_state, {}).get(symbol, set())}
|
|
return current_states
|
|
|
|
def accepts(self, string):
|
|
return any(final_state in self.final_states for final_state in self.get_final_states(string))
|
|
|
|
|
|
nfa = NFA()
|
|
|
|
table = open(sys.argv[1])
|
|
for line in table:
|
|
line = line.rstrip('\n')
|
|
if len(line.split(' ')) == 3:
|
|
a, b, c = line.split(' ')
|
|
c = c.replace("'","")
|
|
c = list(c)
|
|
for x in c:
|
|
nfa.add_transition(a, b, x)
|
|
nfa.alphabet.add(x)
|
|
elif len(line.split(' ')) == 1:
|
|
nfa.add_final_state(line)
|
|
else:
|
|
assert False
|
|
|
|
for line in sys.stdin:
|
|
print("YES" if nfa.accepts(line.strip()) else "NO") |