минимизация dfa в питоне

Question

Я пытаюсь найти алгоритм минимизации DFA в Python.Я нашел несколько примеров, и все они имеют классы в коде.Теперь я не знаю, как пересылать определения DFA, которые помещаются в файл .txt и помещают их в эти классы..txt форматируется следующим образом:

1. строка: набор состояний, разделенных запятой, лексикографически упорядоченный
2. строка: набор символов алфавита, разделенных запятыми, лексикографически упорядоченный
3. строка: набор допустимых состояний, разделенных запятой, лексикографически упорядоченный
4. строка: первое состояние
5. и все остальные строки: передаточная функция в текущем состоянии формата, алфавитсимвол-> следующее состояние

пример определений:

dyny,fllf,gdci,gwtj,knos,kole,mjnw,msdl,mtfz,nbat,njgb,nzwx,rzpn,vcsc,zgfx

b,d,e,f,g,k,l,m,n,o,p,q,r,t,u,w

dyny,njgb,zgfx

mtfz

dyny,b->rzpn

dyny,d->msdl

dyny,e->gdci
.
.
.

пример класса

class DFA:

    def __init__(self, states, alphabet, delta, start, accepts):
        self.states = states
        self.start = start
        self.delta = delta
        self.accepts = accepts
        self.alphabet = alphabet
        self.current_state = start

Я загружаю .txt файл с

f = open('definition.txt','r')

lines = f.readlines()

Answer 1

Пока что это не имеет ничего общего с минимизацией автоматов, верно? Вы пытаетесь создать автомат из некоторого (заданного) формата файла.

Поскольку это домашнее задание, я просто дам вам несколько советов:

readlines возвращает список. Вы можете адресовать определенные строки по индексу, т. Е. lines[0] для первой строки, lines[1], для второй и т. Д. Каждая из этих строк будет строкой. Взяв, например, строку, содержащую набор состояний (lines[0], который содержит 'dyny,fllf,gdci,gwtj,knos,kole,mjnw,msdl,mtfz,nbat,njgb,nzwx,rzpn,vcsc,zgfx'), вы можете использовать

lines[0].split(',')

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

<state>','<input symbol>'->'<next state>

Вы хотите разобрать эти строки, чтобы получить три компонента, показанные выше. string.split снова ваш друг здесь. Вам также следует выбрать подходящую структуру данных для функции перехода (дельта).

Примечание: readlines читает весь файл одновременно. На практике автоматы часто бывают довольно большими, и в этом случае лучше читать файл постепенно. Файловые объекты (f в вашем коде) реализуют протокол итератора и позволяют перебирать строки файла. В частности, я бы предложил использовать

line1 = f.next()  # Next line (first line, if first call of next)
line2 = f.next()  # Next line
...

для первых четырех строк (для получения набора состояний и т. Д.) И для перебора остальных (переходов):

for line in f:
    ...

Подробнее см. http://docs.python.org/tutorial/inputoutput.html.