Quale sarebbe un vero e proprio motore regex reale / DFA risolvere questo semplice schema regex?

Question

Quale sarebbe un vero e proprio motore regex reale / DFA risolvere questo semplice schema regex?

#1 da (6 voti)

0

.*foo

Accademicamente, questa è un'espressione regolare. Una stringa aaaaaaaaaaaaafoo corrisponderà a quella. Anche la stringa aaaaaaaaaaaaafooaaaaafoo corrisponderà anche a quella.

Immagino che un NFA che risolve abbia 4 stati. Lo stato 0 avrà una freccia che torna a se stessa. Quindi una freccia passa allo stato 1, o allo stato 2 e un altro o allo stato 3.

L'NFA manterrà il ciclo fino allo stato 0 prima che utilizzi magicamente il suo potere psichico per decidere aha, ora inizierò a cercare il foo. Tuttavia, ho difficoltà a capire il computer psichico.

Quale sarebbe un DFA? Immagino che il numero di stato sia probabilmente di 6. Quindi un DFA può contenere una variabile booleana, sia che tu stia ancora eseguendo il ciclo o se stia ancora procedendo. Non riesco ancora a capirlo. Quindi qualcuno può aiutarmi a costruire un DFA per questo?

Anche .*foo , ed è variante .*?foo e .*+foo sono espressioni regolari attuali usate oggigiorno in senso non accademico.

In che modo un vero motore regex implementerà queste 3 espressioni? Quanto sono vicine quelle effettive implementazioni al DFA effettivo? Voglio dire, so che i veri DFA non guardano indietro. So anche che il vero motore regex guarda avanti e indietro.

Per motivi di semplicità, supponiamo che DFA contenga variabili anziché solo stati. Penso che gli stati di DFA siano comunque variabili nei ricordi.

regular-expressions

posta user4951 09.11.2015 - 13:25

fonte

1 risposta

Leggi altre domande sui tag regular-expressions

Come è possibile che un programma scriva sulla stessa riga? Python ha alcune caratteristiche che possono essere utilizzate per incapsulare dati privati?

score 6 · Accepted Answer

Con una semplice conversione puoi cambiare un NFA in un DFA prendendo ciascuno stato del DFA come sottoinsieme degli stati NFA. La funzione di transizione prenderebbe ciascuno stato dell'input e otterrà l'insieme degli stati successivi e farà l'unione di tutti loro. Questo modula il computer in più stati contemporaneamente .

Come risultato, il tuo NFA a 4 stati genererebbe un DFA a 4 stati.

Uno stato iniziale {s0} . Ha una transizione con f allo stato successivo {s0, s1} e qualsiasi altro loop torna a se stesso.
uno stato {s0, s1} . Ha una transizione con o allo stato successivo {s0,s2} , una transizione con f a se stessa e ogni altra tornerà a {s0} .
uno stato {s0,s2} Ha una transizione con o allo stato successivo {s0, s3} una transizione con f a {s0, s1} e qualsiasi altro ritornerà a {s0} .
e uno stato di finitura {s0,s3} con una transizione con f a {s0, s1} e tutti gli altri di nuovo a {s0}

Sono possibili più combinazioni di stati (un totale di 2 ^ 4) ma nessuno degli altri è raggiungibile dallo stato iniziale.

Questo è il metodo utilizzato da alcuni regex per evitare il backtracking nell'NFA costruito dalla stringa regex sebbene non sia in grado di modellare i gruppi di cattura e i backrif. È essenzialmente una ricerca mozzafiato nell'NFA.

Altri motori regex (la maggior parte in realtà) fanno fondamentalmente una ricerca in profondità nell'NFA costruito. Ogni volta che sono disponibili più opzioni ne sceglierne una e, se fallisce, prova a tornare a quella decisione e prova l'altro percorso. Quale percorso sceglie per primo viene deciso dal modificatore dell'avidità.