Разработка и реализация DFA в python

Question

У меня возникают проблемы с назначением CS, которое у меня есть в одном из моих классов.

У меня есть язык L, который просто состоит из строк, которые являются URL-адресами, и мне нужно спроектировать и реализовать DFA, который распознает L. (например, www.test.com). Моя проблема прямо сейчас, когда вы читаете все до «www.», Как вы узнаете, когда прекратить чтение для «.com»?

Мой код до сих пор:

s = input("Would you like to input a string? y/n") 
if(s == 'n'): 
    exit 
dfa = {'':{'w':'ww'}, 'w': {'w': 'ww'}, 'ww': {'w': 'www'},'www': {'.': 'www.'},"}} 
def accepts(transitions,initial,accepting,s): 
    state = initial 
    for c in s: 
     state = transitions[state][c] 
    return state in accepting 
accepts(dfa,0,{0},"www.hi.com") 

Любая помощь приветствуется! (Обратите внимание, что я временно заимствуя функцию от here только так я могу понять концепции в игре.

Answer 1

ДКА в основном определяется transition table. Эта таблица переходов отображает каждый (действительный) сочетание текущего состояния и тока вход в соответствующее состояние-преемник.Такую таблицу можно смоделировать как словарь словарей.Например: внешний dict содержит состояния как ключи и словари как значения, эти словари, в свою очередь, имеют действительные входы как ключи и состояние преемника как значение.

EDIT: Ваш выбранный пример не идеален, так как он имеет довольно большой алфавит (т.е. все возможные входные символы) не менее, связанный ответ ограничился [01] по причине ;-) Тем не менее здесь нет, как я бы начать:

{ 
# in state '' we have not yet processed/consumed any input 
# it is the start state 
# the only valid input is a 'w' 
'': {'w': 'w'},  

# in state 'w' we a have already consumed a 'w' 
# the only valid input is another 'w' 
'w': {'w': 'ww'}, 

# in state 'ww' we have previously consumed 'ww' 
# the only valid input is still only a 'w' 
'ww': {'w': 'www'}, 

# now the only valid input is a '.' 
'www': {'.': 'www.'}, 

# this is where your example becomes unpractical: 
# we have to add a transition for every valid input 
# (you could get around this by using a defaultdict and some kind of special signal value, but im not quite sure you are up to that) 
'www.': {'a': 'www.*', 'b': 'www.*', ...}, 

# I used the star in this state name to symbolize multiple (at least one) valid character 
# we only leave this state if we encounter a '.' 
'www.*': {'.': 'www.*.', 'a': 'www.*', 'b': 'www.*', ...}, 

# it should be obvious how to continue from here 
'www.*.': ... 
} 

EDIT2: Реализация после чата.

from collections import defaultdict 

dfa = { 
    'initial': defaultdict(lambda: 'invalid', w='w'), 
    'w': defaultdict(lambda: 'invalid', w='ww'), 
    'ww': defaultdict(lambda: 'invalid', w='www'), 
    'www': defaultdict(lambda: 'invalid', [('.','www.')]), 
    'www.': defaultdict(lambda: 'www.*', [('.','invalid')]), 
    'www.*': defaultdict(lambda: 'www.*', [('.','www.*.')]), 
    'www.*.': defaultdict(lambda: 'www.*', [('c','www.*.c')]), 
    'www.*.c': defaultdict(lambda: 'www.*', [('o','www.*.co')]), 
    'www.*.co': defaultdict(lambda: 'www.*', [('m','www.*.com'), ('.','www.*.')]), 
    'www.*.com': defaultdict(lambda: 'www.*', [('.','www.*.')]), 
    'invalid': defaultdict(lambda: 'invalid') 
} 
def accepts(transitions,initial,accepting,s): 
    state = initial 
    for c in s: 
     state = transitions[state][c] 
     print(c, '->', state) 
    return state in accepting 
print(accepts(dfa,'initial',{'www.*.com', 'www.*.co'},"www.hi.com")) 

Answer 2

Существует ответ here, который объясняет, как это реализовано, но вы также спросить, почему словарь словарей может составлять для различных состояний. Поэтому из этого упомянутого ответа позволяет принимать этот пример:

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

Как вы можете видеть, что первый словарь содержит число 0, 1 и 2, которые являются словарями сами. Это ваши состояния. В их словарях есть персонаж, который будет читать ваш dfa, '0' или '1'. Для тех, кто читает символы, он также дает вам следующее состояние.

Например:

1. Вы начинаете в состоянии 0
2. Читаешь символ '1'
3. Идешь в состояние 1