Es bien sabido que una expresión regular puede ser reconocida por un autómata finito no determinista de tamaño proporcional a la expresión regular, o por un FA determinista que es potencialmente exponencialmente más grande. Además, dada una cadena una expresión regular , la NFA puede probar la pertenencia en tiempo proporcional a, y el DFA puede probar la membresía en un tiempo proporcional a. La desaceleración para el NFA surge del hecho de que esencialmente necesitamos rastrear los conjuntos de estados posibles en los que podría estar el autómata, y la explosión exponencial para el DFA surge del hecho de que sus estados son elementos del conjunto de poder de los estados del NFAr | s | ⋅ | r | El | s |
¿Es posible eficientemente (es decir, en el tiempo mejor que , y espacio mejor que ) reconocer expresiones regulares, si permitimos el uso de máquinas más potentes que autómatas finitos? (Por ejemplo, ¿hay ganancias sucintas al reconocer idiomas regulares con autómatas pushdown o máquinas de contador?)O ( 2 | r | )
fuente
Respuestas:
Es bastante fácil cambiar el tiempo por el espacio, de la siguiente manera.
Convierta la expresión regular en un NFA: para concretar la comparación de algoritmos, asumiremos que es el número de estados NFA, de modo que su tiempo limitado para simular directamente el NFA es válido y su espacio destinado a ejecutar el DFA convertido también es válido siempre que trabaje en una RAM que pueda ocupar tanta memoria.O ( r s ) O ( 2 r )r O(rs) O(2r)
Ahora, divida los estados de la NFA (arbitrariamente) en subconjuntos de como máximo estados cada uno. Dentro de cada subconjunto , podemos indexar los subconjuntos de por números del al .S i ⌈ r / k ⌉ S i A i S i 0 2 ⌈ r / k ⌉ - 1k Si ⌈r/k⌉ Si Ai Si 0 2⌈r/k⌉−1
Construya una tabla donde y están en el rango de 0 a , es un símbolo de entrada y es (el índice numérico de) un subconjunto de . El valor almacenado en la tabla es (el índice numérico de) un subconjunto de : un estado está en si y solo si pertenece a y hay un estado en que transita a en el símbolo de entrada .i j k - 1 c A i S i S j y T [ i , j , c , A i ] y S j A i y cT[i,j,c,Ai] i j k−1 c Ai Si Sj y T[i,j,c,Ai] y Sj Ai y c
Para simular el NFA, mantenga índices, uno para cada , especificando el subconjunto de los estados en que puede alcanzarse mediante algún prefijo de la entrada. Para cada símbolo de entrada , use las tablas para buscar, para cada par , el conjunto de estados en que se puede alcanzar desde un estado en mediante una transición en , y luego use un binario u operación bit a bit los índices numéricos de estos conjuntos de estados para combinarlos en un solo subconjunto de estados de . Entonces, cada paso de la simulación lleva tiempo , y el tiempo total para la simulación esS i A i S i c i , j S j A i c S j O ( k 2 ) O ( s k 2 )k Si Ai Si c i,j Sj Ai c Sj O(k2) O(sk2) .
El espacio requerido es el espacio para todas las tablas, que es . El análisis de tiempo y espacio es válido en cualquier RAM que pueda direccionar tanta memoria y que pueda realizar operaciones binarias en palabras que sean lo suficientemente grandes como para direccionar tanta memoria.O(k22r/k)
La compensación tiempo-espacio que obtienes de esto no coincide perfectamente con la simulación NFA, debido a la dependencia cuadrática de . Pero entonces, soy escéptico de que sea el momento adecuado para la simulación de NFA: ¿cómo simular un solo paso de la NFA más rápido que mirar todas las transiciones (posiblemente cuadráticamente muchas) permitidas desde una actividad actualmente activa? estado a otro estado? ¿No debería ser ?O ( r s ) O ( r 2 s )k O(rs) O(r2s)
En cualquier caso, al permitir que varíe, puede obtener límites de tiempo en un continuo entre los límites de DFA y NFA, con menos espacio que el DFA.k
fuente
Esta no es una respuesta, pero es demasiado larga para un comentario. Estoy tratando de explicar por qué la pregunta, tal como se plantea, puede ser difícil de entender.
Hay dos maneras de definir la complejidad computacional de un dispositivo X .
La primera y más natural es intrínseca . Hay que decir cómo el dispositivo X usa la entrada, para que luego veamos cómo el tamaño n de la entrada afecta el tiempo de ejecución del dispositivo. También hay que decir qué cuenta como una operación (o paso ). Luego, simplemente dejamos que el dispositivo se ejecute en las operaciones de entrada y conteo.
El segundo es extrínseco . Definimos la complejidad computacional para otro dispositivo de Y y luego programamos Y para que actúe como un simulador para X . Dado que puede haber múltiples formas para que Y simule X , debemos agregar que se supone que debemos usar la mejor. Permítanme decir lo mismo con otras palabras: decimos que X toma tiempo en una entrada de tamaño n si existe un simulador de X implementado en la máquina Y que toma tiempo .f ( n )O(f(n)) f(n)
Por ejemplo, una definición intrínseca para NFA dice que se requieren n pasos para procesar una cadena de longitud n ; Una definición extrínseca que utiliza una máquina RAM como dispositivo Y dice que el límite superior más conocido es probablemente lo que respondió David Eppstein. (De lo contrario, sería extraño que (1) la mejor implementación práctica señalada en la otra respuesta no use la mejor alternativa y (2) aquí nadie indique una mejor alternativa). Tenga en cuenta también que estrictamente hablando su dispositivo X es la expresión regular , pero dado que el NFA tiene el mismo tamaño, es seguro tomarlo como el dispositivo X que está viendo.
Entonces, en cierto sentido, la mejor respuesta que puede esperar es una prueba en algo como el modelo de sonda celular de que simular un NFA necesita una cierta cantidad de tiempo. (Tenga en cuenta que si tiene en cuenta la conversión de NFA a DFA, necesita tiempo para anotar el gran DFA, por lo que la memoria no es el único problema allí).
fuente
Incluso si crees que no hay nada nuevo o antiguo que aprender sobre la coincidencia de expresiones regulares, mira uno de los trabajos más bellos que he encontrado en mucho tiempo: una obra de teatro sobre expresiones regulares de S Fischer, F Huch y T Wilke, ICFP 2010.
(MMT Chakravarty merece el crédito por recomendar este documento).
EDITAR: La razón por la cual este artículo es relevante es que describe una nueva técnica (basada en la de Glushkov de los años 60) que evita construir el NFA completo (y mucho menos el DFA) correspondiente al RE. Lo que se hace, en cambio, se asemeja a ejecutar un algoritmo de marcado similar al conocido para decidir la aceptación de una palabra por un NFA en el árbol de sintaxis del RE. Las mediciones de rendimiento sugieren que esto es competitivo, incluso con la biblioteca re2 publicada recientemente por Google.
fuente
Echa un vistazo a este artículo de Russ Cox. Describe un enfoque basado en NFA, empleado por primera vez por Ken Thompson, mediante el cual una cadena de entrada s puede coincidir con una expresión regular r en el tiempo O (| s |. C ) y el espacio O (| r |. D ), donde c y d son constantes superior encuadernados. El artículo también detalla una implementación en C de la técnica.
fuente