Per ottenere direttamente la tua domanda, dovresti fare un breve studio su Chomsky Hierarchy. Questo è un modo vecchio e bello di organizzare linguaggi formali in serie di complessità crescente. Il gradino più basso della gerarchia è il Regular Languages. Potresti indovinare - e avresti ragione - che gli RL sono esattamente quelli che possono essere rappresentati con espressioni regolari "pure": quelli con solo l'alfabeto, la stringa vuota, la concatenazione, l'alternanza | e la stella di Kleene * (guarda Ma, senza riferimenti posteriori). Un teorema classico della teoria del linguaggio formale - Teorema di Kleene - è che i DFA, gli NFA (come descritto nell'articolo citato) e le espressioni regolari hanno tutti esattamente lo lo stesso potere di rappresentare e riconoscere le lingue. La costruzione di Thompson contenuta nell'articolo è una parte della dimostrazione del teorema.
Ogni RL è anche un CFL. Ma ci sono infiniti CFL che non sono regolari. Una caratteristica che può esistere nelle CFL che le rende troppo complesse per essere regolari è una coppia bilanciata di cose: parentesi, blocchi iniziali, ecc. Quasi tutti i linguaggi di programmazione sono CFL. CFL può essere efficacemente riconosciuto da quello che viene chiamato automa pushdown Questo essenzialmente un NFA con un stack incollato su. Lo stack cresce per essere grande quanto necessario, quindi non è più un automa finito. I parser dei linguaggi di programmazione reali sono quasi tutte varianti degli automi pushdown.
consideri l'espressione regolare con backreference
^(b*a)\1$
In parole, questo rappresenta stringhe di lunghezza 2n per qualche n, in cui sia il n'th e personaggi 2n'th sono a e tutti gli altri personaggi sono b. Questo è un perfetto esempio di un CFL che non è regolare. Puoi provarlo rigorosamente con un altro strumento linguistico formidabile chiamato il lemma del pompaggio.
Questo è esattamente il motivo per cui i riferimenti posteriori causano problemi! Consentono "espressioni regolari" che rappresentano lingue non regolari. Pertanto non ci sono NFA o DFA che possano mai riconoscerli.
Ma aspetta, è ancora peggio di quanto abbia fatto per essere così lontano. Considerare
^(b*a)\1\1$
Ora abbiamo una stringa di lunghezza 3n dove il n'th, 2n'th, e gli elementi 3n'th sono a e tutti gli altri sono b. C'è un altro sapore del lemma del pompaggio che consente di dimostrare che questo linguaggio è anche troppo complesso per essere un CFL! Nessun automa pushdown può riconoscere questo.
I riferimenti posteriori consentono a queste espressioni regolari sovralimentate di rappresentare le lingue che sono tre rami nella gerarchia di Chomsky: le lingue sensibili al contesto. In parole povere, l'unico modo per riconoscere un CSL è controllare tutte le stringhe nella lingua di uguale lunghezza (almeno se P! = NP, ma questo è vero per tutti gli scopi pratici e una storia completamente diversa). Il numero di tali stringhe è esponenziale nella lunghezza di quella che stai cercando.
Questo è il motivo per cui è necessario il regex matcher di ricerca. Puoi essere molto intelligente nel modo in cui progetta la ricerca. Ma ci sarà sempre qualche input che lo spinge a prendere tempo esponenziale.
Quindi sono d'accordo con l'autore dell'articolo che hai citato. È possibile scrivere regex dall'aspetto perfettamente innocente con senza riferimenti posteriori che verrà riconosciuto in modo efficace per quasi tutti gli input, ma dove esiste qualche input che causa un matcher di espressioni regolari Perl o Java o Python - perché è una ricerca di backtracking - per richiedere milioni di anni per completare la partita. Questo è pazzesco. Puoi avere uno script che è corretto e funziona bene per anni e poi si blocca un giorno solo perché è incappato in uno dei cattivi input. Supponiamo che l'espressione regolare è sepolto nel messaggio parser del sistema di navigazione a bordo del velivolo si sta in sella ...
Modifica
Su richiesta, io abbozzo come il lemma di pompaggio può essere usata per dimostrare la lingua a^k b a^k b non è regolare. Qui a^k è una scorciatoia per a ripetuta k volte. Il PL dice che deve esistere un intero positivo N tale che ogni stringa in un linguaggio regolare di lunghezza almeno N debba essere nella forma R S T tale che R S^k T sia anche nella lingua per tutto il k naturale. Qui R, , T sono stringhe e S potrebbe non essere vuoto.
La prova del PL dipende dal fatto che ogni lingua normale corrisponde ad alcuni DFA. Un input accettato per questo DFA più lungo del suo numero di stati (che equivale a L nel lemma) deve causarlo a "loop:" per ripetere uno stato. Chiama questo stato X. La macchina consuma una stringa R per andare dall'inizio a X, quindi S per tornare a X, quindi T per arrivare ad uno stato accettante.Bene, l'aggiunta di copie aggiuntive di S (o l'eliminazione di S) nell'input corrisponde solo a un numero diverso di "loop" da X a X. Di conseguenza, sarà accettata anche la nuova stringa con copie aggiuntive (o cancellate) di S .
Dal ogni RL deve soddisfare il PL, una prova che una lingua non è procede regolarmente dimostrando che esso contraddice il PL. Per la nostra lingua, questo non è difficile. Supponiamo che tu stia cercando di convincermi della lingua L = a^k b a^k b che soddisfi il PL. Perché lo fa, devi essere in grado di darmi un valore di N (vedi sopra): il numero di stati in un ipotetico DFA che riconosce L. A quel punto, dirò, "Ok Mr. Guy normale, considera il stringa B = a^N b a^N b. " Se L è regolare, B deve causare questo DFA (indipendentemente dall'aspetto) per eseguire il ciclo all'interno dei primi N caratteri, che devono essere tutti a s! Quindi il ciclo (stringa S sopra) è costituito da tutti gli a s, anche. Con questo posso immediatamente mostrare che la tua affermazione che L è regolare è falsa. Ho solo scelto di fare il giro una seconda volta. Ciò causerà questo ipotetico DFA di accettare una nuova stringa a^M b a^N b, dove M> N perché ho aggiunto a s alla sua prima metà. Ahia! Questa nuova stringa non è in L, quindi il PL non è vero dopo tutto. Dal momento che posso fare questo trucco ogni volta, non importa quale N hai fornito, il PL non può tenere per L, e L non può essere regolare dopo tutto.
Dal momento che non è regolare, il teorema di Kleene ci dice non c'è DFA né FA né espressione regolare "pura" che lo descrive.
La prova che torna arbitri consentire lingue che non sono nemmeno contesto libero è un anello molto simile, ma ha bisogno di background su automi a pila che io non ho intenzione di dare qui. Google fornirà.
NB: Entrambe queste non sono a prova del fatto che i riferimenti posteriori rendono il riconoscimento NP completo. Si limitano a dire in modo molto rigoroso che i refi aggiungono complessità reale a pure espressioni regolari. Consentono alle lingue che non possono essere riconosciute con nessuna macchina con memoria finita, né nessuna con una memoria LIFO infinitamente grande. Lascerò la prova della completezza NP agli altri.
Il tipo di articolo di risposte giuste, regex con backrefs non è un'espressione regolare, è la definizione formale. Anche se questo non risponde perché un algoritmo così veloce non può essere fatto per una regex con backrefs. – Qtax