¿Se detienen todas las expresiones regulares?

Question

¿Hay alguna expresión regular que, para algunas cadenas de entrada, busque una coincidencia para siempre?

Answer 1

Para una entrada finita, no hay una expresión regular formal que no se detenga.

Cualquier expresión regular formal se puede traducir a un autómata finito determinista. Un DFA lee la entrada de un carácter a la vez y, al final de la entrada, está en un estado de aceptación o en un estado de no aceptación. Si el estado lo acepta, la entrada coincide con la expresión regular. De lo contrario, no es así.

Ahora, la mayoría de las bibliotecas de "expresiones regulares" admiten cosas que no son expresiones regulares, como las referencias anteriores.Siempre que se mantenga alejado de esas características y tenga una entrada finita, se le garantiza que se detenga. Si no lo hace ... dependiendo de lo que está utilizando exactamente, es posible que no se le garantice el alto. Perl permite que se inserte código arbitrario, por ejemplo, y no se garantiza que se detenga el código arbitrario equivalente a máquina-máquina.

Ahora, si la entrada es infinita, entonces se pueden encontrar expresiones regulares triviales que nunca se detendrán. Por ejemplo, ".*".

Answer 2

No en el sentido que está describiendo, puede tener algunas expresiones regulares muy ineficientes que toman muchos recursos y terminan matando el motor de expresiones regulares, esto no es lo mismo que detenerse.

No creo que suspender realmente se aplica aquí, como los otros comentaristas de esta publicación han señalado tan astutamente. http://en.wikipedia.org/wiki/Halting_problem

Answer 3

De acuerdo con this question, se detienen todas las expresiones regulares.

Answer 4

Imagino que no es posible encontrar una expresión regular que no se detenga.

El tamaño de su entrada es finito. El tamaño máximo de cualquier subgrupo coincidente de la expresión regular es, como máximo, el tamaño de su entrada.

A menos que el algoritmo utilizado sea bastante estúpido (repasando casos varias veces), el número de subgrupos coincidentes también será finito.

Por lo tanto, se detendrá.

Answer 5

No puedo imaginar una cadena de entrada que se analizaría para siempre, aunque una cadena infinitamente larga se analizaría para siempre. Dado que una expresión regular puede describir un lenguaje regular, que es potencialmente un conjunto infinito de palabras, una expresión regular puede describir un lenguaje de palabras infinitas, incluidas las palabras de longitud infinita. Sin embargo, ninguna cadena de entrada puede ser infinitamente larga, por lo que en algún momento tendría que detenerse.

Por ejemplo, si a * b es aceptado en el idioma, y ​​usted tiene una cadena infinitamente larga de 'a's, entonces sí, la expresión regular nunca se detendrá. Prácticamente, sin embargo, esto es imposible.

Answer 6

La expresión regular formal es en realidad un método para describir un autómata finito determinista para analizar cadenas. La expresión regular "coincide" si el DFA termina en un estado de aceptación al final de la entrada. Como el DFA lee su entrada de forma secuencial, siempre se detendrá cuando llegue al final de la entrada, y si existe o no coincidencia es simplemente una cuestión de examinar en qué estado del DFA se detiene.

La coincidencia de subcadenas es la misma, excepto que en lugar de forzarse a detenerse al final de una lectura de la cadena, el DFA se forzará a detenerse después de leer cada posible subcadena una vez; sigue siendo un caso finito. (Sí, la mayoría de los motores regex implementan esto de una manera un poco más optimizada que simplemente arrojando todas las subcadenas posibles en un DFA, pero conceptualmente el límite sigue ahí).

Por lo tanto, el único caso posible en el que el DFA no se detiene es si la entrada fue infinita, lo que generalmente se considera fuera del alcance del problema de detención.

Answer 7

Sí.

Una expresión regular se puede representar mediante una máquina de estados finitos. Cada vez que reciba una entrada atómica, hará que cualquier FSM bien definido pase a un estado conocido.

La excepción es cuando tiene entrada infinita, pero esto no es aplicable al problema de detención porque se trata de entrada finita. Cuando tiene una máquina de estados finitos y una entrada finita, siempre es posible determinar si su máquina se detendrá o no.

http://en.wikipedia.org/wiki/Finite_state_machine

Answer 8

+1 para la respuesta de Daniel: todas las entradas finitos verdadera causa de expresión regular (es decir, sin referencias hacia atrás u otras características no expresiones regulares) para detener, y de expresiones regulares son equivalentes a DFA.

Bono: Coincidencia de expresiones regulares puede ser simple y rápida (pero es lento en Java, Perl, PHP, Python, Ruby, ...)

http://swtch.com/~rsc/regexp/regexp1.html

Tenga en cuenta que los dos gráficos en el la parte superior del artículo tiene escalas diferentes en el eje y: uno es segundos, el otro es microsegundos!