Как конечные автоматы реализованы в коде?

Прямым способом представления DFA является словарь словарей. Для каждого состояния создайте словарь, который вводится буквами алфавита, а затем глобальным словарем, который вводится в соответствие с состояниями. Например, следующий DFA из статьи в Википедии о DFA

может быть представлен следующим словарем:

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

Для «запуска» dfa против входной строки, взятой из рассматриваемого алфавита (после указания начального состояния и набора принимаемых значений) является простым:

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

Вы начинаете в исходном состоянии, набираете символ строки по символу и на каждом шаге просто смотрите следующее состояние. Когда вы закончите переходить через строку, вы просто проверяете, находится ли конечное состояние в наборе принимающих состояний.

Например

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

Для NFA вы можете хранить наборы возможных состояний, а не отдельные состояния в словарях перехода, и использовать random модуль для выбора следующего состояния из множества возможных состояний.

Итак, здесь я представляю рекурсивное решение для NFA.

рассмотрим следующую nfa:

переходы могут быть представлены с использованием списка списков следующим образом:

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

Примечание. Состояние 4 является гипотетическим состоянием. Когда вы перейдете в это состояние, вы не сможете двигаться дальше. Это полезно, если вы не можете прочитать ввод из текущего состояния. Вы напрямую переходите в состояние 4 и говорите, что ввод не принят для текущего прогресса (проверьте другие возможности, вернувшись). например, если вы находитесь на q1 , а текущий входной символ – 'a' , вы переходите в состояние 4 и продолжаете вычислять дальше.

вот код 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() 

sample output: (строки, заканчивающиеся на abb, принимаются)

 enter the string: abb accepted enter the string: aaaabbbb rejected 

……