concevoir et implémenter un DFA en python

Question

J'ai des problèmes avec un devoir CS que j'ai dans une de mes classes.

J'ai un langage L, qui consiste simplement en des chaînes qui sont des URL, et je dois concevoir et implémenter un DFA qui reconnaît L. (par exemple: www.test.com). Mon problème en ce moment est, une fois que vous avez lu dans tout jusqu'à 'www.', Comment sauriez-vous quand arrêter de lire pour le ".com"?

Mon code à ce jour:

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") 

Toute aide est appréciée! (Notez que je suis temporairement emprunter une fonction de here juste pour que je puisse comprendre les concepts en jeu.

Answer 1

Un DFA est essentiellement définie par un transition table. Ce tableau de transition cartes de chaque (valide) combinaison de l'état actuel et le courant entrée dans l'état successeur correspondant Une telle table peut être modélisée comme un dictionnaire de dictionnaires Par exemple: La dict externe contient les états comme clés et les dictionnaires comme valeurs, ces dictionnaires ont à leur tour les entrées valides comme clés et l'état successeur valeur

EDIT: L'exemple choisi n'est pas idéal, en ce sens qu'il a un alphabet assez grand (tous les caractères d'entrée possibles) d'au moins [a-zA-Z0-9], la réponse liée se limitait à [01] pour une raison ;-) Jamais moins voici comment je commencerais:

{ 
# 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: Mise en œuvre après le chat.

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

Il y a une réponse here qui explique comment cela est mis en œuvre, mais vous demandez aussi pourquoi un dictionnaire des dictionnaires peut représenter des états différents. Donc, de cette réponse mentionnée permet de prendre cet exemple:

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

Comme vous pouvez le voir le premier dictionnaire contient les numéros 0, 1 et 2, qui sont eux-mêmes dictionnaires. Ce sont les états. Dans leurs dictionnaires, il y a un caractère que votre dfa va lire, '0' ou '1'. Pour ces caractères lus, il vous donne également votre prochain état.

Par exemple:

1. Vous commencez à l'état 0
2. Vous avez bien lu caractère '1'
3. Vous allez à l'état 1