¿Qué algoritmos existen para construir un DFA que reconozca el lenguaje descrito por una expresión regular dada?

11

Todos mis libros de texto usan el mismo algoritmo para producir un DFA dado un regex: primero, haga un NFA que reconozca el idioma del regex, luego, usando la construcción del subconjunto (también conocido como "powerset"), convierta el NFA en un DFA equivalente ( opcionalmente minimizando el DFA). También una vez escuché a un profesor aludir a que había otros algoritmos. ¿Alguien sabe de alguna? ¿Quizás uno que va directamente de la expresión regular a un DFA sin el NFA intermedio?

BlueBomber
fuente
Bienvenido a cstheory, un sitio de preguntas y respuestas para preguntas de nivel de investigación en informática teórica (TCS). Su pregunta no parece ser una pregunta de nivel de investigación en TCS. Consulte las preguntas frecuentes para obtener más información sobre lo que significa esto. Su pregunta podría ser adecuada para la informática que tiene un alcance más amplio.
Kaveh
1
¿Por qué siempre usas este comentario de plantilla? Aparentemente hay al menos 5 que no están de acuerdo contigo. Te sugiero que le des una oportunidad a estas preguntas.
AJed
@AJed, no siempre uso este comentario. Lo uso cuando una pregunta me parece fuera de tema pero podría ser adecuada para la informática . El aumento de votos no significa que una pregunta sea sobre el tema, y ​​esta no parece ser una pregunta de nivel de investigación para mí, por lo que creo que el comentario es apropiado. (El hecho de que alguien pueda escribir una respuesta de nivel de investigación a una pregunta no hace que la pregunta sea de nivel de investigación). Pd: Creo que esta discusión es más adecuada para el Meta teórico de la informática .
Kaveh

Respuestas:

13

Existen diferentes algoritmos para convertir expresiones regulares en autómatas finitos. Puede pasar directamente de expresiones regulares a DFA sin construir ningún otro autómata primero haciendo implícitamente la construcción del subconjunto mientras genera el autómata. Otra opción para obtener directamente autómatas deterministas es utilizar el método de derivados.

Verificar si una expresión regular representa el lenguaje que contiene todas las cadenas es un problema completo de PSPACE (vea esta respuesta para una referencia). Comprobar si un DFA acepta que el lenguaje se puede hacer en tiempo polinómico, por lo que si pasa directamente de una expresión regular a un DFA, habrá una explosión en alguna parte.

Mi comprensión de la literatura es que podemos elegir traducciones que nos permitan localizar la explosión. Es decir, hay diferentes formas de pasar de una expresión regular a un autómata finito, y se prefieren los métodos que son lineales o polinómicos. Por lo general, los costos exponenciales se empujan a la determinación de autómatas.

Se ha trabajado mucho para identificar subfamilias de expresiones regulares a partir de las cuales podemos generar DFA de manera eficiente . Esta línea de trabajo depende de la traducción que use. Es decir, arregla una asignación de expresiones regulares a NFA e intenta caracterizar las expresiones regulares que se asignan a DFA.

La construcción estándar de autómatas a partir de expresiones regulares no es la construcción preferida en dicho trabajo. Las construcciones de elección producen autómatas que se parecen mucho a la estructura de la expresión regular. Estas construcciones usan la noción de una derivada de una expresión regular.

Derivadas de expresiones regulares , JA Brzozowski. 1964.

srara

Derivados parciales de expresiones regulares y construcciones de autómatas finitos , V. Antimirov. 1995

Si piensa en el estado de un autómata como una representación de todas las cadenas aceptadas desde ese estado, los derivados (parciales) le permiten tratar las expresiones regulares como estados . Contrasta con la construcción de libros de texto estándar que trata intuitivamente las expresiones regulares como autómatas, no estados.

De expresiones regulares a autómatas deterministas , G. Berry y R. Sethi, 1986.

Berry y Sethi discuten explícitamente la correspondencia entre las expresiones regulares y los estados de un autómata y el determinismo, que combinan la noción de derivados de Brzozowski con la idea de distinguir entre ocurrencias del mismo símbolo para dar una traducción basada en la sintaxis de expresiones regulares en finito. autómatas

Lenguas regulares no ambiguas , A. Brüggemann-Klein y Derick Wood, 1998.

Este documento se basa en trabajos anteriores de Brüggemann-Klein y estudia casos en los que puede usar derivados para generar DFA en tiempo polinómico. Hay una gran cantidad de trabajo después de este documento. Fue significativo desde la perspectiva de las tecnologías web porque las expresiones regulares que pueden manipularse de manera eficiente (también conocido como DFA) fueron importantes para procesar SGML y XML.

Se ha trabajado mucho para estudiar otros casos especiales de expresiones regulares deterministas. Un artículo muy reciente que estudia cuándo se pueden resolver algunos de estos problemas en tiempo lineal es de 2012.

Expresiones regulares deterministas en tiempo lineal , Benoit Groz, Sebastian Maneth, Slawomir Staworko. 2012

Vijay D
fuente
55
Ya ha mencionado derivados en su respuesta, por lo que también debe agregar JA Brzozowski: Derivados de expresiones regulares, Journal of the ACM 11 (4): 481–494 (1964), ya que proporciona un algoritmo directo para convertir expresiones regulares a DFA .
Neel Krishnaswami
3
Debatí sobre eso. Pero los tres documentos anteriores se basan directamente en ese resultado, así que pensé que no había razón para mencionarlo. El artículo de Brueggeman-Klein y Wood también está lleno de ejemplos. Si menciono a Brzozowski, creo que también debería mencionarse a Antimirov. Quería evitar una encuesta, pero tal vez debería hacerlo. ¿Que dice?
Vijay D
55
Si tiene el tiempo y la energía, creo que aquí son muy apropiadas las respuestas largas de encuestas.
David Eppstein
1
@VijayD: sí, estoy de acuerdo con David. Las respuestas cortas están bien, pero si tienes la energía, es bueno dar una respuesta integral.
Neel Krishnaswami