Entwerfen und Implementieren eines DFA in Python

Question

Ich habe Probleme mit einer CS-Zuweisung, die ich in einer meiner Klassen habe.

Ich habe eine Sprache L, die einfach aus Strings besteht, die URLs sind, und ich muss ein DFA entwerfen und implementieren, das L. erkennt (z. B. www.test.com). Mein Problem ist jetzt, wenn Sie alles bis auf das "www." Gelesen haben, wie würden Sie wissen, wann Sie aufhören sollten, für die ".com" zu lesen?

Mein Code so weit:

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

Jede Hilfe ist willkommen! (Beachten Sie, dass ich einfach so eine Funktion aus here borgen ich die Konzepte im Spiel verstehen vorübergehend bin.

Answer 1

Ein DFA grundsätzlich durch ein transition table definiert ist. Karten Dieser Übergang Tabelle, die jede (gültig) Kombination von aktuellen Stand und aktuelle Eingabe in den entsprechenden Nachfolgestatus Eine solche Tabelle kann als Dictionary von Dictionaries modelliert werden, zB: Das äußere Diktat enthält die Zustände als Schlüssel und Wörterbücher als Werte, diese wiederum haben die gültigen Eingaben als Schlüssel und den Nachfolgerzustand als Wert

EDIT: Ihr gewähltes Beispiel ist nicht ideal, so dass es ein ziemlich großes Alphabet (dh alle möglichen Eingabezeichen) von mindestenshat, die verknüpfte Antwort beschränkte sich auf [01] aus einem Grund ;-) Nichts desto trotz ist hier, wie ich anfangen würde:

{ 
# 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: nach Chat-Implementierung.

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

Es gibt eine Antwort here, die erklärt, wie dies umgesetzt wird, aber Sie auch fragen, warum ein Wörterbuch der Wörterbücher für verschiedene Zustände erklären kann. Also von dieser erwähnten Antwort lässt dieses Beispiel nehmen:

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

Wie Sie das erste Wörterbuch sehen kann, enthält die Zahlen 0, 1 und 2, die Wörterbücher selbst sind. Dies sind Ihre Staaten. In ihren Wörterbüchern befindet sich ein Zeichen, das Ihr dfa lesen wird, '0' oder '1'. Für diese gelesenen Zeichen gibt es Ihnen auch Ihren nächsten Zustand.

Zum Beispiel:

1. Sie beginnen im Zustand 0
2. Sie gelesene Zeichen '1'
3. Sie gehen in den Zustand 1