Как я могу выбрать правильное состояние в NFA - PullRequest
Новая
       25

Как я могу выбрать правильное состояние в NFA

0 голосов
/ 12 января 2020

У меня проблема с NFA. Я попытался реализовать это, но что, если у нас будет ситуация, как на картинке с первым l oop - например, мы можем выбрать q0 или q1, если мы начнем с символа 0; enter image description here 

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 без списка состояний. Как я могу выбрать правильный путь?

1 Ответ

1 голос
/ 12 января 2020

NFA может находиться в нескольких состояниях одновременно.

Вы можете исправить это в своем __init__ с помощью: 

self.current_state = set([start_state])

и в transition_to_state_with_input рассмотрите каждый из возможные текущие состояния. 

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

Это также изменит in_accept_state на что-то вроде 

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