12
Esiste un'espressione regolare che, per qualche stringa di input, cercherà una corrispondenza per sempre?Tutte le espressioni regolari si fermano?
A
risposta
31
Per un input limitato, non esiste un'espressione regolare formale che non si arresti.
Qualsiasi espressione regolare formale può essere tradotta in un automatico finito deterministico. Un DFA legge l'input di un carattere alla volta e, alla fine dell'input, sei in uno stato di accettazione o in uno stato di non accettazione. Se lo stato sta accettando, l'input corrisponde all'espressione regolare. Altrimenti no.
Ora, la maggior parte delle librerie di "espressioni regolari" supportano le cose che non sono espressioni regolari, come i riferimenti posteriori.Finché ti allontani da quelle funzioni e hai un input limitato, ti viene garantito un arresto. Se non ... a seconda esattamente di quello che si sta usando, potrebbe non essere garantito un arresto. Perl consente di inserire codice arbitrario, ad esempio, e non è garantito il blocco di codice arbitrario, equivalente alla macchina di turing.
Ora, se l'input è infinito, è possibile trovare espressioni regolari banali che non si fermeranno mai. Ad esempio, ".*".
+0
+1 per menzionare riferimenti di ritorno. – Brian
+3
L'unico cavillo: sono chiamati automi finiti deterministici, non definiti. In contrasto con (ironicamente, equivelant) automi finiti non deterministici. – agorenst
+0
@Agor: I * lo odio * quando lo faccio. Sono ben consapevole del nome corretto, ma scrivo sempre il nome sbagliato per qualche motivo. :-( –
1
Non nel senso che stai descrivendo, puoi avere alcune espressioni regolari molto inefficienti che occupano un sacco di risorse e finiscono per uccidere il motore regex, questo non equivale a fermarsi.
Non credo che l'interruzione si applichi davvero qui, come gli altri commentatori di questo post hanno così astutamente sottolineato. http://en.wikipedia.org/wiki/Halting_problem
+1
Non c'è un modo per fare un programma che, per ogni possibile programma, ti dirà se si ferma o meno. Ma ciò non significa che non puoi farlo per un sottoinsieme. Forse le regex sono uno di questi sottoinsiemi, ma non lo so. – hsribei
+1
In riferimento al problema dell'arresto qui non è molto utile; l'algoritmo utilizzato per la corrispondenza RE è un particolare algoritmo, la cosa interessante del problema dell'arresto è risolverlo per tutte le coppie di input del programma. –
+0
(wow! Esatto stesso secondo!) –
1
In base a this question, ogni espressione regolare si arresta.
2
Immagino, non è possibile trovare un'espressione regolare che non si fermi.
La dimensione dell'input è limitata. La dimensione massima di qualsiasi sottogruppo abbinato dell'espressione regolare è, al massimo, la dimensione del tuo input.
A meno che l'algoritmo utilizzato sia piuttosto stupido (andando oltre i casi più volte), anche il numero di sottogruppi corrispondenti sarà finito.
Quindi, si fermerà.
0
Non riesco a immaginare una stringa di input che verrà analizzata per sempre, sebbene una stringa infinitamente lunga venga analizzata per sempre. Dato che un'espressione regolare può descrivere un linguaggio regolare, che è potenzialmente un insieme infinito di parole, una regex può descrivere un linguaggio di parole infinite, incluse parole di lunghezza infinita. Tuttavia, nessuna stringa di input può essere infinitamente lunga, quindi a un certo punto dovrebbe fermarsi.
Ad esempio, se un * b è accettato nella lingua e si dispone di una stringa infinitamente lunga di 'a', allora sì, la regex non si arresterà mai. In pratica, però, questo è impossibile.
7
L'espressione regolare formale è in realtà un metodo di descrizione di un automa finito deterministico per l'analisi di stringhe. La regex "corrisponde" se il DFA si conclude in uno stato di accettazione alla fine dell'input. Dal momento che il DFA legge il suo input in sequenza, si fermerà sempre quando raggiunge la fine dell'input e se c'è o meno una corrispondenza è semplicemente una questione di esaminare a quale stato del DFA si ferma.
La corrispondenza delle sottostringhe è effettivamente la stessa, ma invece di essere forzata a fermarsi alla fine di un read-through della stringa, il DFA sarebbe invece costretto a fermarsi dopo aver letto ogni possibile sottostringa una volta - ancora un caso finito. (Sì, la maggior parte dei motori regex lo implementa in un modo un po 'più ottimizzato rispetto al semplice lancio di ogni sottostringa possibile in un DFA - ma concettualmente il limite è ancora lì).
Pertanto, l'unico caso possibile in cui il DFA non si fermerebbe è se l'input fosse infinito, che è generalmente considerato oltre lo scopo del problema di interruzione.
0
Sì.
Un'espressione regolare può essere rappresentata da una macchina a stati finiti. Ogni volta che si riceve un input atomico, qualsiasi FSM ben definito passerà a uno stato noto.
L'eccezione è quando si ha un input infinito, ma questo non è applicabile al problema di interruzione perché riguarda l'input finito. Quando hai una macchina a stati finiti e un input finito, è sempre possibile determinare se la tua macchina si fermerà o meno.
0
+1 la risposta di Daniel: tutti gli ingressi finiti causa del vero regolare (cioè senza backreference o altre caratteristiche non regex) per fermare e regex sono equivalenti a DFA.
Bonus: Regular Expression corrispondenza può essere semplice e veloce (ma è lento in Java, Perl, PHP, Python, Ruby, ...)
http://swtch.com/~rsc/regexp/regexp1.html
Si noti che i due grafici alla all'inizio dell'articolo hanno scale diverse sull'asse delle ordinate: una è secondi, l'altra è microsecondi!
... e si può scrivere un programma che determina se una regex si arresta o meno per un dato input? –
Per i marchi bonus - utilizzando un'espressione regolare! –
Certo, mmyers e mgb - basta eseguire questo contro l'input concatenato alla regex: /.*/ - match significa che si ferma, nessuna corrispondenza significa che non lo fa. : P – Amber