58 lines
1.5 KiB
Python
58 lines
1.5 KiB
Python
import sys
|
|
|
|
sys.setrecursionlimit(4500)
|
|
|
|
def AddTransition(transitions, state_from, state_to, symbol):
|
|
if state_from in transitions:
|
|
if symbol not in transitions[state_from]:
|
|
transitions[state_from][symbol] = {state_to}
|
|
else:
|
|
transitions[state_from][symbol] |= {state_to}
|
|
else:
|
|
transitions[state_from] = {symbol: {state_to}}
|
|
|
|
def AddFinalState(final_states, state):
|
|
final_states.add(state)
|
|
|
|
def GetFinalState(transitions, final_states, string, current_state):
|
|
if not string:
|
|
return current_state if current_state in final_states else -1
|
|
|
|
symbol, rest = string[0], string[1:]
|
|
|
|
try:
|
|
for state in transitions[current_state][symbol]:
|
|
result = GetFinalState(transitions, final_states, rest, state)
|
|
if result != -1:
|
|
return result
|
|
except KeyError:
|
|
return -1
|
|
|
|
return -1
|
|
|
|
def IsAccepted(transitions, finalStates, string, initial_state):
|
|
finalState = GetFinalState(transitions, finalStates, string, initial_state)
|
|
return finalState in finalStates
|
|
|
|
|
|
transitions = {}
|
|
finalStates = {2}
|
|
|
|
AddTransition(transitions, 0, 0, 'a')
|
|
AddTransition(transitions, 0, 0, 'b')
|
|
AddTransition(transitions, 0, 0, 'c')
|
|
AddTransition(transitions, 0, 1, 'b')
|
|
AddTransition(transitions, 1, 2, 'a')
|
|
AddTransition(transitions, 1, 2, 'b')
|
|
AddTransition(transitions, 1, 2, 'c')
|
|
|
|
|
|
for line in sys.stdin:
|
|
line = line.rstrip()
|
|
|
|
if IsAccepted(transitions, finalStates, line, 0):
|
|
print('YES')
|
|
else:
|
|
print('NO')
|
|
|