I'm writing an NFA (nondeterministic finite automaton) class, which should parse a given input and returns all possible traces (paths from the initial to the final state). Ultimately, I want to calculate the degree of ambiguity of a given automaton.
Unfortunately, I'm not able to collect the return of the method properly. This version of the code returns None
and a slightly modified one using yield
returns only the one, the first, path.
This question seems somewhat vague, but I hope someone can give me a hint in the right direction.
Thanks in advance.
class NFA(object):
__slots__ = [
'states',
'alphabet',
'transitions',
'initial_state',
'final_states',
]
#
#
# -------- Init -----------
#
def __init__(
self,
states: set,
alphabet: set,
transitions: dict,
initial_state: str,
final_states: set,
):
"""
Initialize a complete automaton.
"""
self.states = states
self.alphabet = alphabet
self.transitions = transitions
self.initial_state = initial_state
self.final_states = final_states
#
#
# -------- process -----------
#
def process(self, word: str, trace: list = []) -> list:
"""
Check if the given string is accepted by this automaton.
Return all accepting paths.
"""
# processing finished returning the trace
if (not word):
print(trace)
return trace
# start processing with initial state
if (not trace):
trace.append(self.initial_state)
# get the current state transitions
state_transition: dict = self.transitions.get(trace[-1], None)
# input not accepted
if (not state_transition):
return False
# iterate over each possible transition
for state in state_transition.get(word[0], []):
# create new sub trace, append current state
sub_trace: list = trace.copy()
sub_trace.append(state)
# start recursive function call
self.process(word[1:], trace=sub_trace)
from automata.nfa import NFA
config: dict = {
'states': ['q0', 'q1', 'q2'],
'alphabet': ['a'],
'transitions': {
'q0': {
'a': ['q1', 'q2']
},
'q1': {
'a': ['q1']
}
},
'initial_state': 'q0',
'final_states': ['q1'],
}
testNFA = NFA(**config)
assert testNFA.process("a") == [['q0', 'q1'], ['q0', 'q2']]