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

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?

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.

$s$$r$$a$$r$$a$

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