W jaki sposób automaty skończone są zaimplementowane w kodzie?

Question

Jak można wdrożyć dfa lub nfa w tej sprawie w kodzie Pythona?

Co można zrobić w pythonie? Czy są one kiedykolwiek używane w projektach realnych?

Answer 1

Prostym sposobem reprezentowania DFA jest słownik słowników. Dla każdego stanu utwórz słownik, który jest oznaczony literami alfabetu, a następnie globalnym słownikiem, który jest wpisany przez stany. Na przykład, co następuje DFA z Wikipedia article on DFAs

może być reprezentowany przez słowniku jak poniżej:

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

Do „run” DFA przeciwko ciąg wejściowy pobierany z alfabetu w pytaniu (po określeniu stanu początkowego i zestawu wartości akceptowanych) jest proste:

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

Zaczynasz w stan początkowy, krok po znaku ciąg znaków po znaku, a na każdym kroku po prostu wyszukaj następny stan. Po zakończeniu przechodzenia przez ciąg po prostu sprawdź, czy stan końcowy znajduje się w zbiorze stanów akceptujących.

Na przykład

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

Dla NFAs można przechowywać zestawy możliwych stanów zamiast pojedynczych stanów przejściowych w słownikach i wykorzystać moduł random odebrać następnego stanu ze zbioru możliwych stanów.

Answer 2

cóż, tutaj przedstawiam rozwiązanie rekurencyjne dla NFA.

rozważyć następujące NFA:

przejścia mogą być reprezentowane przy użyciu listy list następująco:

przejścia = [[[0,1],[0]], [[4],[2]], [[4],[3]], [[4],[4]],[[4],[4]]]

Uwaga: State 4 jest hipotetyczny stan. Gdy przejdziesz do tego stanu, nie będziesz mógł się dalej poruszać. Jest to pomocne, gdy nie można odczytać danych wejściowych z bieżącego stanu. Bezpośrednio przechodzisz do stanu 4 i mówisz, że wejście nie jest akceptowane dla bieżącego postępu (sprawdź inne możliwości, cofając się). np. jeśli jesteś na q1, a bieżący symbol wejściowy to 'a', przechodzisz do stanu 4 i przerwiesz dalsze przetwarzanie.

oto kod 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() 

wyjście próbki: (ciągi zakończone ABB są akceptowane)

enter the string: abb 
accepted 

enter the string: aaaabbbb 
rejected 

......