Come vengono implementati gli automatismi finiti nel codice?

Question

Come si implementa uno dfa o uno nfa per quella materia in codice Python?

Quali sono alcuni buoni modi per farlo in python? E sono mai stati usati in progetti del mondo reale?

Answer 1

Un modo semplice per rappresentare un DFA è come un dizionario di dizionari. Per ogni stato creare un dizionario che è digitato dalle lettere dell'alfabeto e quindi un dizionario globale che è digitato dagli stati. Ad esempio, il seguente DFA dal Wikipedia article on DFAs

può essere rappresentato da un dizionario come questo:

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

Per "run" un dfa contro una stringa di input tratto dalla alfabeto in questione (dopo aver specificato lo stato iniziale e l'insieme di valori accettabili) è semplice:

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

Si inizia nel stato iniziale, passa attraverso la stringa carattere per carattere, e ad ogni passaggio cerca semplicemente lo stato successivo. Quando hai finito di scavalcare la stringa, controlla semplicemente se lo stato finale è nell'insieme degli stati di accettazione.

Per esempio

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

Per NFA è possibile memorizzare set di possibili stati, piuttosto che i singoli Stati nei dizionari transizione e utilizzare il modulo random di scegliere lo stato successivo dal set di stati possibili.

Answer 2

bene, qui presento una soluzione ricorsiva per NFA.

considerare il seguente NFA:

le transizioni possono essere rappresentati utilizzando l'elenco di liste come segue:

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

Nota: Stato 4 è un ipotetico stato. Una volta che vai in quello stato, non puoi andare oltre. È utile quando non puoi leggere l'input dallo stato corrente. Si passa direttamente allo stato 4 e si dice che l'input non è accettato per il progresso corrente (controllare altre possibilità tornando indietro). ad esempio, se sei a q1 e il simbolo di input corrente è 'a', vai allo stato 4 e interrompi il calcolo ulteriormente.

ecco il codice 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() 

esempio di output: (sono accettate le stringhe che terminano con ABB)

enter the string: abb 
accepted 

enter the string: aaaabbbb 
rejected 

......