从文本文件为确定性有限自动机创建Python字典

Question

我想用python创建一个程序来执行自动机显示的功能。自动机的工作如图所示。

我想让程序适合我想要的每个自动机。因此，我有描述给定自动机的dfa.txt。

dfa.txt

3       //Number of states of the DFA
0 1     //Accepted characters
0       //initial state
0 1     //final state
0 1 1   //If the automaton is in state q0 and reads 1 it goes to state q1 
0 0 0   //If the automaton is in state q0 and reads 0 it goes to state q0
1 1 2   //If the automaton is in state q1 and reads 1 it goes to state q2
1 0 0   //If the automaton is in state q1 and reads 0 it goes to state q0
2 1 2   //If the automaton is in state q2 and reads 1 it goes to state q2
2 0 2   //If the automaton is in state q2 and reads 0 it goes to state q2

我面临的问题是，我无法将其转换为适合自动机显示的字典。我知道我可以在dfa.py类文件中创建字典，但该程序必须适用于文本文件。我应该如何转换成字典并使其在我的代码中起作用？

这是我到目前为止所拥有的。

n = 'y'
def readFile(): #function that is intended to create a dictionary from the text file
    dictionary = {}
    with open('dfa.txt', 'r') as dict:
            for line in dict:
                    a,b,c = line.split()    #line split
                    dictionary[a] = int(b)  #matching the first column of the text file with the wanted transisions 
                    dictionary[a] = int(c)  #matching the first column of the text file with the wanted transisions 
            return dictionary
while n != 'n':                 #loop  for multiple checks
    s = input('\n' + 'Enter the string: ')

    def accepts(transitions,initial,accept,accepting,s):    #(transisions from dictionary,initial state, final state, final state, string) 
            state = initial
            for c in s:                                 #checking all the possible transisions for the inputed string from the dictionary
                    state = transitions[state][c]
            if(state in accept or state in accepting):  #if the transisions end in a accepted from the dictionary final state prints True
                    print (True)
            else:
                    print (False)
#accepts(dictionary,0,{4},{5},s)            #Excecution

    n = input('\n' + 'Do you want to enter a new string?(y/n): ')   #Option for new input

Answer 1

首先，您需要考虑代表整个自动机的数据结构。

让我们看一个具有两个状态q0, q1和两个符号0, 1的简单自动机。我将抛出一个标志'T'，以表明它的终端是否进入了每种状态，都是很好的措施。

a = { "q0": {
              0: "q1",
              1: "q0",
             'T': False
            },
      "q1": {
              0: "q0",
              1: "q1",
             'T': True
            }
    }

如果它处于状态q1，并且接收到1作为输入，则它必须保持在状态q1。非常简单。基本上，next_state = dictionary[current_state][the_received_symbol]

现在很容易看到如何从文本文件创建它并使用：

n = 'y'
def generate_automaton():
    """Generates the dictionary and returns it along with initial state
    """
    dictionary = {}
    with open('dfa.txt', 'r') as dict:
        states = dict.next()  # number of states
        for s in range(states):
            # Generate dictionary for each state
            # none of them are terminal yet
            dictionary[s] = {'T': False}

        dict.next()  # Accepted characters - don't need them

        initial = dict.next()  # Initial state

        final_states = dict.next().split()
        for s in final_states:
            # Now mark terminal states
            dictionary[s]['T'] = True

        for l in dict:
            # Fill the transition table from the rest of the file
            current, symbol, nxt = l.split()
            dictionary[current][symbol] = nxt

        return initial, dictionary

initial, auto = generate_automaton()  # We need to actually generate one

while n != 'n':                 #loop  for multiple checks
    current_state = initial
    s = input('\n' + 'Enter the string: ')
    # Here your code becomes incomprehensible, so I'll just assume that you
    # take a string of accepted characters and print True if you end up in a
    # terminal state.

    for symbol in s:
        current_state = auto[current_state][symbol]
    print(auto[current_state]['T'])

    n = input('\n' + 'Do you want to enter a new string?(y/n): ')