Quais algoritmos existem para a construção de um DFA que reconheça a linguagem descrita por um determinado regex?

Todos os meus livros usam o mesmo algoritmo para produzir um DFA dado um regex: primeiro, faça um NFA que reconheça o idioma do regex e, usando a construção do subconjunto (também conhecido como "powerset"), converta o NFA em um DFA equivalente ( opcionalmente, minimizando o DFA). Também ouvi uma vez um professor aludir a outros algoritmos. Alguém sabe de algum? Talvez um que vá diretamente do regex para um DFA sem o NFA intermediário?

Existem algoritmos diferentes para converter expressões regulares em autômatos finitos. Você pode ir diretamente de expressões regulares para DFAs sem criar nenhum outro autômato primeiro, fazendo implicitamente a construção do subconjunto enquanto gera o autômato. Outra opção para obter diretamente autômatos determinísticos é usar o método de derivadas.

Verificar se uma expressão regular representa o idioma que contém todas as strings é um problema completo do PSPACE (consulte esta resposta para obter uma referência). Verificando se um DFA aceita que o idioma possa ser feito em tempo polinomial, portanto, se você passar diretamente de uma expressão regular para um DFA, haverá uma explosão em algum lugar.

Minha compreensão da literatura é que podemos escolher traduções que nos permitam localizar a explosão. Ou seja, existem diferentes maneiras de passar de uma expressão regular para um autômato finito, e os métodos lineares ou polinomiais são preferidos. Geralmente, os custos exponenciais são empurrados para a determinação de autômatos.

Houve muito trabalho na identificação de subfamílias de expressões regulares a partir das quais podemos gerar DFAs com eficiência . Essa linha de trabalho depende da tradução que você usa. Ou seja, você corrige um mapeamento de expressões regulares para NFAs e tenta caracterizar as expressões regulares que são mapeadas para DFAs.

A construção padrão de autômatos a partir de expressões regulares não é a construção preferida nesse trabalho. As construções de escolha produzem autômatos que se assemelham à estrutura da expressão regular. Essas construções usam a noção de um derivado de uma expressão regular.

Derivadas de expressões regulares , JA Brzozowski. 1964

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

Derivadas Parciais de Expressões Regulares e Construções de Autômatos Finitos , V. Antimirov. 1995.

Se você pensa no estado de um autômato como uma representação de todas as seqüências de caracteres aceitas nesse estado, as derivações (parciais) permitem tratar expressões regulares como estados . Contraste com a construção padrão de livros didáticos que trata intuitivamente expressões regulares como autômatos, não estados.

De expressões regulares a autômatos determinísticos , G. Berry e R. Sethi, 1986.

A correspondência entre expressões regulares e estados de um autômato e determinismo é discutida explicitamente por Berry e Sethi, que combinam a noção de derivadas de Brzozowski com a idéia de distinguir ocorrências do mesmo símbolo para fornecer uma tradução baseada em sintaxe de expressões regulares em expressões finitas. autômatos.

Linguagens Regulares Um-inequívocas , A. Brüggemann-Klein e Derick Wood, 1998.

Este artigo baseia-se em trabalhos anteriores de Brüggemann-Klein e estuda casos em que você pode usar derivadas para gerar DFAs em tempo polinomial. Há uma grande quantidade de trabalho após este documento. Foi significativo do ponto de vista das tecnologias da Web, porque expressões regulares que podem ser manipuladas com eficiência (também conhecidas como DFAs) eram importantes para o processamento de SGML e XML.

Há muito trabalho estudando outros casos especiais de expressões regulares determinísticas. Um artigo muito recente que estuda quando alguns desses problemas podem ser resolvidos em tempo linear é de 2012.

Expressões regulares determinísticas em tempo linear , Benoit Groz, Sebastian Maneth, Slawomir Staworko. 2012.