en minimisant dfa en python

Question

J'essaie de trouver un algorithme pour minimiser DFA en python. J'ai trouvé quelques exemples et ils ont tous des classes dans le code. Maintenant, je ne sais pas comment transférer les définitions de DFA qui sont placées dans le fichier .txt et les mettre dans ces classes. .txt est formatée sur le chemin suivant:

1. ligne: L'ensemble des états séparés par une virgule, lexicographiquement commandé
2. ligne: un ensemble de symboles d'alphabet séparés par des virgules, lexicographiquement commandé
3. ligne: L'ensemble des états acceptables séparés par une virgule, lexicographiquement commandé
4. ligne: le premier état
5. et toutes les autres lignes: fonction de transfert dans le format état actuel, Alphabet symbolisation> état suivant

exemple des définitions:

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 
. 
. 
. 

exemple de classe

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 

je charger le fichier txt avec

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

lines = f.readlines() 

Answer 1

Jusqu'à présent, cela n'a rien à voir avec minimazation des automates, non? Vous essayez de créer un automate à partir d'un format de fichier donné.

Puisque c'est un devoir, je vais vous donner quelques conseils:

readlines retourne une liste. Vous pouvez adresser des lignes spécifiques par index, c'est-à-dire, lines[0] pour la première ligne, lines[1], pour la seconde, etc. Chacune de ces lignes sera une chaîne. En prenant, par exemple, la ligne contenant l'ensemble des états (lines[0], qui détient 'dyny,fllf,gdci,gwtj,knos,kole,mjnw,msdl,mtfz,nbat,njgb,nzwx,rzpn,vcsc,zgfx'), vous pouvez utiliser

lines[0].split(',')

de le diviser par une virgule, ce qui vous donne une liste de chaînes, dont chacun représente un état. Ces lignes qui représentent les transitions individuelles suivent un format un peu plus compliqué:

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

Vous voulez analyser ces lignes afin que vous obtenez les trois composants décrits ci-dessus. string.split est encore votre ami ici. Vous devriez également décider d'une structure de données appropriée pour la fonction de transition (delta).

Remarque: readlines lit le fichier entier en une fois. En pratique, les automates sont souvent assez gros, auquel cas il serait préférable de lire le fichier de façon incrémentielle. Les objets de fichier (f dans votre code) implémentent le protocole itérateur et vous permettent d'itérer sur les lignes du fichier.En particulier, je suggère d'utiliser

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

pour les quatre premières lignes (pour obtenir l'ensemble des états, etc.) et à itérer sur le reste (les transitions):

for line in f: 
    ... 

Voir http://docs.python.org/tutorial/inputoutput.html pour plus de détails.