Как распечатать все автоматные пути, начинающиеся с данного слова? - PullRequest
Новая
       61

Как распечатать все автоматные пути, начинающиеся с данного слова?

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

Я пытаюсь написать программу, которая проверяет, принято ли данное слово определенным автоматом c и, если это так, выводит все пути, начинающиеся с этого слова (со следующим символом ":") , Например, для слова «собака» мы ищем пути, начинающиеся с «собака», например: собака: собака: hieuhvi et c. Если такого пути нет, должно быть напечатано следующее сообщение: dog: nothing.

Автомат выглядит следующим образом: 

0 1 d
1 2 o
2 3 g
3 4 :
4 5 a
5

, что означает, что 0 является начальным состоянием, 5 принимает состояние и с вводом «собака» я должен получить вывод «собака: а».

Я уже пытался кодировать часть, которая обрабатывает формат автомата и проверяет, принято ли слово 

transition = dict()
acceptingState = []
symbols = []
listA = []
words = []

for line in sys.stdin:
    line = line.split()
    if len(line) == 1:
        acceptingState.append(line[0])
    elif len(line) == 3 or len(line) == 4:
        if line[2] not in  symbols:
            symbols.append(line[2])
        if (int(line[0]), line[2]) not in transitions:
            transitions[(int(line[0]), line[2])] = line[1]

и он работает отлично, но у меня есть проблема с частью, отвечающей за поиск различных путей для данного слова. 

def checking(word):
    initialState = 0
    wordList = list(word)
    for x in wordList:
        if ((initialState, x)) in transitions:
            transition = transitions[(initialState, x)]
            initialState = int(transition)
        else:
            print(word + ":nothing")
    func(word, transitions, initialState, [])
    for x in words:
      print(word + x)

def func(word, graph, node, visited):
    if str(node) in acceptingState:
        word = "".join(visited)
        words.append(word)
    for symbol in symbols:
        if ((int(node), symbol)) in graph:
            n = graph[int(node), symbol]
            listA = visited[:]
            listA.append(symbol)
            func(word, graph, int(n), listA[:])

with open(sys.argv[1]) as file:
    for line in file:
        line = line.rstrip("\n")
        checking(line)

Проблема с этим кодом состоит в том, что я всегда получаю dogmth: N instad of dog : N, а также я получаю собаку: ничего несколько раз.

Что я должен изменить здесь?

...