Comment les automates finis sont-ils implémentés dans le code?

Question

Comment implémenter un dfa ou un nfa d'ailleurs en code Python?

Quels sont les bons moyens de le faire en python? Et sont-ils utilisés dans des projets concrets?

Answer 1

Une manière simple de représenter un DFA est un dictionnaire de dictionnaires. Pour chaque état, créez un dictionnaire qui est saisi à l'aide des lettres de l'alphabet, puis un dictionnaire global qui est saisi par les états. Par exemple, le DFA suivant de la Wikipedia article on DFAs

peut être représenté par un dictionnaire comme celui-ci:

dfa = {0:{'0':0, '1':1}, 
     1:{'0':2, '1':0}, 
     2:{'0':1, '1':2}} 

« Exécuter » DFA contre une chaîne d'entrée tirée de l'alphabet en question (après avoir spécifié l'état initial et l'ensemble des valeurs acceptantes) est simple:

def accepts(transitions,initial,accepting,s): 
    state = initial 
    for c in s: 
     state = transitions[state][c] 
    return state in accepting 

Vous commencez dans le état initial, parcourez la chaîne caractère par caractère et à chaque étape, recherchez simplement l'état suivant. Lorsque vous avez fini de parcourir la chaîne, vous vérifiez simplement si l'état final est dans l'ensemble des états acceptants.

Par exemple

>>> accepts(dfa,0,{0},'1011101') 
True 
>>> accepts(dfa,0,{0},'10111011') 
False 

Pour NFAs vous pouvez stocker des ensembles d'états possibles plutôt que des États individuels dans les dictionnaires de transition et utiliser le module random pour choisir l'état suivant de l'ensemble des états possibles.

Answer 2

bien, ici je présente une solution récursive pour NFA.

considèrent la NFA suivante:

les transitions peuvent être représentés en utilisant la liste des listes comme suit:

transition = [[[0,1],[0]], [[4],[2]], [[4],[3]], [[4],[4]],[[4],[4]]]

Note: Etat 4 est un hypothétique Etat. Une fois que vous allez dans cet état, vous ne pouvez pas aller plus loin. C'est utile quand vous ne pouvez pas lire l'entrée de l'état actuel. Vous allez directement à l'état 4 et dites que l'entrée n'est pas acceptée pour la progression en cours (vérifiez les autres possibilités en revenant en arrière). Par exemple, si vous êtes au q1 et que le symbole d'entrée actuel est 'a', vous passez à l'état 4 et arrêtez le calcul.

ici est le code Python:

#nfa simulation for (a|b)*abb 
#state 4 is a trap state 


import sys 

def main(): 
    transition = [[[0,1],[0]], [[4],[2]], [[4],[3]], [[4],[4]]] 
    input = raw_input("enter the string: ") 
    input = list(input) #copy the input in list because python strings are immutable and thus can't be changed directly 
    for index in range(len(input)): #parse the string of a,b in 0,1 for simplicity 
     if input[index]=='a': 
      input[index]='0' 
     else: 
      input[index]='1' 

    final = "3" #set of final states = {3} 
    start = 0 
    i=0 #counter to remember the number of symbols read 

    trans(transition, input, final, start, i) 
    print "rejected" 



def trans(transition, input, final, state, i): 
    for j in range (len(input)): 
     for each in transition[state][int(input[j])]: #check for each possibility 
      if each < 4:        #move further only if you are at non-hypothetical state 
       state = each 
       if j == len(input)-1 and (str(state) in final): #last symbol is read and current state lies in the set of final states 
        print "accepted" 
        sys.exit() 
       trans(transition, input[i+1:], final, state, i) #input string for next transition is input[i+1:] 
     i = i+1 #increment the counter 


main() 

sortie exemple: (cordes se terminant par abb sont acceptées)

enter the string: abb 
accepted 

enter the string: aaaabbbb 
rejected 

......