如何实现一种算法,该算法创建一个元组列表,这些元组包含嵌套字典中的特定值

您好,我正在尝试实现非确定性有限自动机算法。

给定字典,开始状态和输入列表,我输入第一个 输入值进入开始状态。根据字典'ndfa' 我收到一组新状态(ndfa [state] [_ input]-> {n_states})。

然后,我从输入列表移至下一个输入值并输入 从先前的输入值接收到的新状态之一。然后添加 到process_lst。

然后,我在另一状态下测试相同的输入值 以前收到过(如果我收到的不止一个)。否则我就进入 输入列表中的下一个输入,并在新给定的输入上重复该过程 状态。

如果输入对于当前状态是非法的 (不是当前状态过渡的关键), 只是忽略它。但是如果输入没有可能的状态 (空状态集)终止处理。

这就是我现在正在尝试的。

ndfa = {'start': {'0': {'near', 'start'},'1': {'start'}},
'near': {'1': {'end'}},
'end': {}}

state = 'start'
inputs = ['1','0','1','1','0','1']


def process(ndfa : {str:{str:{str}}}, state : str, inputs : [str]) -> [None]:
    process_list = [state]
    new_possible_states = {state}

    for _input in inputs:
        for _state in new_possible_states:
            process_list.append((_input, ndfa[_state][_input]))
    new_possible_states = ndfa[_state][_input]

return process_list



if __name__ == '__main__':
    print(process(ndfa,state, inputs))

正确的process_list输出:

['start',('1',{'start'}),('0',{'near','start'}),('1',{'end','start'}))( '1',{'start'}),('0',{'near','start'}),('1',{'end','start'})]

Visual of Algorithm:
  Start state = start
    Input = 1; new possible states = ['start']
    Input = 0; new possible states = ['near', 'start']
    Input = 1; new possible states = ['end', 'start']
    Input = 1; new possible states = ['start']
    Input = 0; new possible states = ['near', 'start']
    Input = 1; new possible states = ['end', 'start']
  Stop state(s) = ['end', 'start']
评论