regex - expresiones - expresion regular or

DFA vs NFA engines: ¿Cuál es la diferencia en sus capacidades y limitaciones?

Question

Estoy buscando una explicación no técnica de la diferencia entre DFA vs NFA motores, en función de sus capacidades y limitaciones.

Answer 1

Aquí hay una respuesta no técnica de Microsoft:

Los motores DFA se ejecutan en tiempo lineal porque no requieren retroceso (y por lo tanto nunca prueban el mismo carácter dos veces). También pueden garantizar que coincida con la cadena más larga posible. Sin embargo, dado que un motor de DFA contiene solo estado finito, no puede coincidir con un patrón con referencias retrospectivas, y como no construye una expansión explícita, no puede capturar subexpresiones.

Los motores tradicionales de NFA ejecutan los llamados algoritmos de seguimiento retroactivo "codiciosos", probando todas las posibles expansiones de una expresión regular en un orden específico y aceptando la primera coincidencia. Debido a que un NFA tradicional construye una expansión específica de la expresión regular para una coincidencia exitosa, puede capturar coincidencias de subexpresión y hacer correspondencias de referencias. Sin embargo, debido a que un NFA retrocede, puede visitar exactamente el mismo estado varias veces si se llega al estado en diferentes rutas. Como resultado, puede ejecutarse exponencialmente lentamente en el peor de los casos. Debido a que un NFA tradicional acepta la primera coincidencia que encuentra, también puede dejar otras coincidencias (posiblemente más largas) sin descubrir.

Los motores POSIX NFA son como los motores NFA tradicionales, excepto que continúan retrocediendo hasta que puedan garantizar que han encontrado la coincidencia más larga posible. Como resultado, un motor POSIX NFA es más lento que un motor NFA tradicional, y cuando usa un POSIX NFA no puede favorecer una coincidencia más corta que una más larga cambiando el orden de la búsqueda de rastreo.

Los programadores prefieren los motores tradicionales NFA porque son más expresivos que los motores DFA o POSIX NFA. Aunque en el peor de los casos pueden funcionar con lentitud, puede dirigirlos para encontrar coincidencias en tiempo lineal o polinomial utilizando patrones que reducen las ambigüedades y limitan el retroceso.

[http://msdn.microsoft.com/en-us/library/0yzc2yb0.aspx]

Answer 2

Encuentro que la explicación dada en Expresiones regulares, El tutorial completo de Jan Goyvaerts es la más útil. Ver la página 7 de este PDF:

https://www.princeton.edu/~mlovett/reference/Regular-Expressions.pdf

Entre otros puntos hechos en la página 7, hay dos tipos de motores de expresiones regulares: motores dirigidos por texto y motores dirigidos por expresiones regulares. Jeffrey Friedl los llama motores DFA y NFA, respectivamente. ... ciertas características muy útiles, como los cuantificadores perezosos y las referencias retrospectivas, solo pueden implementarse en motores dirigidos a expresiones regulares.

Answer 3

Las Automatizaciones finitas deterministas (DFA) y las Automatizaciones finitas no deterministas (NFA) tienen exactamente las mismas capacidades y limitaciones. La única diferencia es la conveniencia de la notación.

Un autómata finito es un procesador que tiene estados y lecturas de entrada, cada carácter de entrada puede establecerlo en otro estado. Por ejemplo, un estado podría ser "solo leer dos C en una fila" o "estoy empezando una palabra". Estos generalmente se utilizan para escaneos rápidos de texto para encontrar patrones, como el escaneo léxico del código fuente para convertirlo en símbolos.

Un autómata finito determinista está en un estado a la vez, que es implementable. Un autómata finito no determinista puede estar en más de un estado a la vez: por ejemplo, en un lenguaje donde los identificadores pueden comenzar con un dígito, puede haber un estado "leyendo un número" y otro estado "leyendo un identificador", y un NFA podría estar en ambos al mismo tiempo cuando lee algo que comienza en "123". El estado que realmente se aplica dependerá de si encuentra algo que no sea numérico antes del final de la palabra.

Ahora, podemos expresar "leyendo un número o identificador" como un estado en sí mismo, y de repente no necesitamos el NFA. Si expresamos combinaciones de estados en un NFA como estados, tenemos un DFA con muchos más estados que el NFA, pero que hace lo mismo.

Es una cuestión de la cual es más fácil leer, escribir o tratar. Los DFA son más fáciles de entender per se, pero los NFA son generalmente más pequeños.

Answer 4

Tanto los NFA como los DFA son autómatas finitos, como dicen sus nombres.

Ambos pueden representarse como un estado de inicio, un estado de éxito (o "aceptar") (o un conjunto de estados de éxito) y una tabla de estado que enumera las transiciones.

En la tabla de estados de un DFA, cada <state₀, input> pasará a uno y solo a un state₁ .

En la tabla de estado de un NFA, cada <state₀, input> pasará a un conjunto de estados.

Cuando toma un DFA, reinícielo a su estado de inicio, una secuencia de símbolos de entrada, y sabrá exactamente en qué estado final está y si es un estado de éxito o no.

Sin embargo, cuando tome un NFA, buscará, para cada símbolo de entrada, el conjunto de posibles estados de resultados, y (en teoría) al azar, no determinísticamente, seleccionará uno de ellos. Si existe un conjunto de selecciones aleatorias que conducen a uno de los estados de éxito para esa cadena de entrada, se dice que el DFA tiene éxito para esa cadena. En otras palabras, se espera que pretendas que mágicamente siempre selecciona el correcto.

Una primera pregunta en informática fue si las NFA eran más poderosas que los DFA, debido a esa magia, y la respuesta resultó ser negativa, ya que cualquier NFA podría traducirse en un DFA equivalente. Sus capacidades y limitaciones son exactamente iguales entre sí.

Answer 5

Una explicación simple, no técnica, parafraseada del libro de Jeffrey Friedl Mastering Regular Expressions .

CAVEAT :

Si bien este libro generalmente se considera la "Biblia regex", parece existir cierta controversia sobre si la distinción hecha aquí entre DFA y NFA es realmente correcta. No soy científico informático, y no entiendo la mayor parte de la teoría detrás de lo que realmente es una expresión "regular", determinista o no. Después de que comenzó la controversia, eliminé esta respuesta debido a esto, pero desde entonces se ha mencionado en los comentarios de otras respuestas. Estaría muy interesado en discutir esto más a fondo. ¿Puede ser que Friedl realmente esté equivocado? ¿O me equivoqué con Friedl (pero volví a leer ese capítulo ayer por la noche, y es como lo recuerdo ...)?

Editar: parece que Friedl y yo estamos equivocados. Por favor revisa los excelentes comentarios de Eamon a continuación.

Respuesta original:

Un motor de DFA pasa por la cadena de entrada carácter por carácter e intenta (y recuerda) todas las formas posibles en que la expresión regular podría coincidir en este punto. Si llega al final de la cadena, declara éxito.

Imagine la cadena AAB y la expresión regular A*AB . Ahora revisamos nuestra letra de cadena por letra.

1. A :

   • Primera sucursal: se puede combinar con A* .
   • Segunda rama: se puede hacer coincidir ignorando la A* (se permiten cero repeticiones) y usando la segunda A en la expresión regular.

2. A :

   • Primera ramificación: puede combinarse expandiendo A* .
   • Segunda ramificación: no puede ser igualada por B La segunda rama falla. Pero:
   • Tercera rama: puede combinarse al no expandir A* y usar la segunda A lugar.

3. B :

   • Primera rama: no se puede combinar expandiendo A* o moviendo en la expresión regular al siguiente token A La primera rama falla.
   • Tercera rama: se puede combinar. ¡Hurra!

Un motor DFA nunca retrocede en la cadena.

Un motor de NFA pasa por el token de expresión regular mediante token e intenta todas las permutaciones posibles en la cadena, retrocediendo si es necesario. Si llega al final de la expresión regular, declara el éxito.

Imagine la misma cadena y la misma expresión regular que antes. Ahora pasamos por nuestro token de expresiones regulares por token:

1. A* : Match AA . Recuerde las posiciones de retroceso 0 (comienzo de la cuerda) y 1.
2. A : no coincide. Pero tenemos una posición de retroceso a la que podemos regresar e intentar nuevamente. El motor de expresiones regulares retrocede un caracter. Ahora coincide con A
3. B : Partidos. Se alcanzó el final de la expresión regular (con una posición de retroceso para sobrar). ¡Hurra!