40 lines
1.4 KiB
Python
40 lines
1.4 KiB
Python
import sys
|
|
|
|
class FSA:
|
|
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_all_paths(self):
|
|
paths = []
|
|
stack = [('', '0')]
|
|
while stack:
|
|
current_path, current_state = stack.pop()
|
|
if current_state in self.final_states:
|
|
paths.append(current_path)
|
|
if current_state in self.transitions:
|
|
for symbol, states in self.transitions[current_state].items():
|
|
stack.extend((current_path + symbol, state) for state in states)
|
|
return sorted(paths)
|
|
|
|
fsa = FSA()
|
|
|
|
for line in sys.stdin:
|
|
parts = line.strip().split('\t')
|
|
if parts == ['']: break
|
|
[fsa.add_transition(parts[0], parts[1], parts[2]) for parts in [parts]] if len(parts) == 3 else fsa.add_final_state(parts[0])
|
|
for path in fsa.get_all_paths():
|
|
print(path) |