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

11

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?

BlueBomber
fonte
Bem-vindo ao cstheory, um site de perguntas e respostas para perguntas em nível de pesquisa em ciência da computação teórica (TCS). Sua pergunta não parece ser uma pergunta em nível de pesquisa no TCS. Consulte as Perguntas frequentes para obter mais informações sobre o significado disso. Sua pergunta pode ser adequada para Ciência da Computação, que tem um escopo mais amplo.
Kaveh
1
por que você sempre usa esse comentário de modelo? Aparentemente, existem pelo menos cinco que não concordam com você. Eu sugeriria que você desse uma chance a essas perguntas.
AJed
@AJed, eu nem sempre uso esse comentário. Uso-o quando uma pergunta parece fora de tópico para mim, mas pode ser adequada para a Ciência da Computação . O voto positivo não significa que uma pergunta esteja no tópico, e esta não parece ser uma pergunta em nível de pesquisa para mim, então acho que o comentário é apropriado. (O fato de alguém poder escrever uma resposta em nível de pesquisa para uma pergunta não a torna em nível de pesquisa.) Ps: Eu acho que essa discussão é mais adequada para o meta teórico da ciência da computação .
Kaveh

Respostas:

13

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

srara

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.

Vijay D
fonte
5
Você já mencionou derivadas em sua resposta, portanto, também deve adicionar JA Brzozowski: Derivadas de expressões regulares, Journal of the ACM 11 (4): 481–494 (1964), pois ele fornece um algoritmo direto para converter regexps em DFAs .
Neel Krishnaswami
3
Eu debati sobre isso. Mas todos os três documentos acima se baseiam diretamente nesse resultado, então pensei que não havia razão para mencioná-lo. O artigo Brueggeman-Klein e Wood também está cheio de exemplos. Se eu mencionar Brzozowski, acho que Antimirov também deve ser mencionado. Eu queria evitar uma pesquisa, mas talvez eu devesse fazer isso. O quê dizer?
Vijay D
5
Se você tiver tempo e energia, acho que respostas longas e semelhantes a pesquisas são muito apropriadas aqui.
David Eppstein
1
@VijayD: sim, eu concordo com o David. Respostas curtas são boas, mas se você tiver energia, é bom dar uma resposta abrangente.
Neel Krishnaswami