如何在NFA中选择正确的状态

Question

我对NFA有问题。我试着实现这个，但是如果我们在第一个循环的图片上有这样的情况会怎样？例如，如果我们以0符号开始，我们可以选择q0或q1；

def __init__(self, states, alphabet, transition_function, start_state, accept_states):
    self.states = states
    self.alphabet = alphabet
    self.transition_function = transition_function
    self.start_state = start_state
    self.accept_states = accept_states
    self.current_state = start_state
    return

def transition_to_state_with_input(self, input_value):
    if (self.current_state, input_value) not in self.transition_function.keys():
        self.current_state = None
        return
    self.current_state = self.transition_function[(self.current_state, input_value)]
    return

def in_accept_state(self):
    return self.current_state in accept_states

def go_to_initial_state(self):
    self.current_state = self.start_state
    self.list_of_state.append(self.current_state)
    print("\tactual state: " + self.current_state)
    return

def run_with_input_list(self, input_list):
    self.go_to_initial_state()
    for inp in input_list:
        self.transition_to_state_with_input(inp)
        print("\tinput symbol: " + inp)
        print("\tactual state: " + str(self.current_state))
        if self.current_state is not None:
            self.list_of_state.append(self.current_state)
        continue
    print(self.list_of_state)
    self.list_of_state.clear()
    return self.in_accept_state()

pass

输出：

INPUT: 112
    actual state: q0
    input symbol: 1
    actual state: ('q0', 'q2')
    input symbol: 1
    actual state: None
    input symbol: 2
    actual state: None
['q0', ('q0', 'q2')]
False

在这种情况下，我们的实际状态应该是q2，没有状态列表。我怎样才能选择正确的方法

Answer 1

NFA可以同时处于多个状态

您可以在__init__中用以下方法更正此问题：

self.current_state = set([start_state])

和在{{CD2>}中考虑每个可能的当前状态。

def transition_to_state_with_input(self, input_value):
    new_state = set()
    for state in self.current_state:
         # get the new possible states and add them to the new_state set
    self.current_state = new_state

这也会在_accept _状态中发生变化，例如

def in_accept_state(self):
    return len(self.current_state & set(accept_states)) >= 1