Um autômato finito não determinístico (NDFA) pode ser convertido eficientemente em um autômato finito determinístico (DFA) no espaço / tempo subexponencial?

16

Vinte anos atrás, criei um pacote de expressões regulares que incluía conversões de expressões regulares em uma máquina de estado finito (DFA) e oferecia suporte a uma série de operações fechadas de expressões regulares (estrela Kleene, concatenação, reversão, operações de conjunto etc.). Eu não tinha certeza do pior desempenho do meu pacote.

Um DFA tem o mesmo poder expressivo que um NDFA, porque um NDFA de estado n pode ser trivialmente convertido em um DFA com 2 ^ n estados. No entanto, existem garantias de limite superior inferior para essa conversão que não exijam uma explosão exponencial no estado?

Não pude apresentar exemplos de expressões regulares de mau comportamento ou NDFAs, mas não gastei muito tempo pensando nisso. Eu estou supondo uma expressão regular como ((((| | A | B | C) * (e | D | E | F)) * (e | G | H | I)) * (e | J | K | L | M)) *, que mistura muitas alternâncias e as estrelas Kleene teriam um NDFA de tamanho linear, mas um DFA expansivo.

Wesner Moise
fonte
Existem restrições sobre a classe de NFAs que você gostaria de aceitar como entrada? Algumas restrições levam a melhores limites superiores.
András Salamon
não é um ponto muito importante, mas precisa que o ndfa seja sua própria tag?
Lev Reyzin
Sim, existem restrições. Os NFAs são construídos diretamente a partir de expressões regulares, tratando-os como gráficos de transição generalizados. seas.upenn.edu/~cit596/notes/dave/regexp-nfa4.html
Wesner Moise

Respostas:

15

Sabe-se que, para cada par de números naturais de n,atal modo que n <= a <= 2^n, existe um NDFA mínima com nestados cujas dfa mínimo equivalente correspondente tem aestados (ao longo de um de quatro letras do alfabeto).

Veja o artigo aqui: Explosões determinísticas de autômatos finitos não-determinísticos mínimos sobre um alfabeto fixo .

Resumo do trabalho:

Mostramos que para todos os números n e α de tal forma que n ≤ α ≤ 2 ^ n, existe um autômato finito não determinístico mínimo de n estados com um alfabeto de entrada de quatro letras cujo autômato finito determinístico mínimo equivalente possui exatamente um estado. Daqui resulta que, no caso de um alfabeto de quatro letras, não existem "números mágicos", isto é, os buracos na hierarquia. Isso melhora um resultado semelhante obtido por Geffert para um alfabeto crescente de tamanho n + 2 (Proc. 7 DCFS, Como, Itália, 23-37).

Então, suponho que a resposta para sua pergunta seja não.

Aryabhata
fonte
a questão é solicitar um "algoritmo" em execução no espaço e no tempo subexponencial para converter o NFA.
Marcos Villagra
@Marcos: Se sua saída é exponencial, você não pode ter um algoritmo que é executado em tempo subexponencial.
Aryabhata
11
Este é um resultado geral. Se houver restrições conhecidas na classe de NFAs de entrada, talvez seja possível fazer melhor.
András Salamon
@ Andras: Concordo, mas dado que isso provavelmente está relacionado à programação (que suportará Kleen * etc), duvido que o conjunto de entradas NFA seja restrito a um subconjunto adequado.
Aryabhata
5
Este resultado foi recentemente reforçada para usar um de três letras do alfabeto, e as construções são um pouco mais simples: portal.acm.org/...
13

O exemplo clássico de um idioma com uma separação exponencial entre o tamanho do DFA e o tamanho do NFA é o seguinte idioma finito: cadeias binárias de comprimento exatamente 2n, nas quais a primeira metade não é igual à segunda metade. Um NFA adivinharia um índice i no qual a primeira e a segunda metade discordam. Um limite inferior para um DFA segue da complexidade da comunicação, por exemplo.

Noam
fonte
8

O DFA mínimo correspondente a um NFA possui 2 ^ n estados no pior caso, portanto, você não pode garantir nada. Sem um exemplo construtivo, o raciocínio é que em um NFA você pode estar em qualquer subconjunto arbitrário de estados após a leitura de uma determinada sequência de entrada, e cada um desses subconjuntos pode se comportar de maneira diferente ao observar um caractere. Suponha um idioma com dois caracteres no alfabeto (aeb) e um NFA N com n estados que comece com um estado de aceitação em s_0. Agora enumere todos os subconjuntos de estados de N e construa a tabela de transição de forma que a observação "a" do subconjunto S_i leve você ao subconjunto S_i + 1 e a observação b o leve ao subconjunto S_i-1 (isso é possível para algumas enumerações, acho ) Agora, esse autômato possui n estados e aceita seqüências de ma e nb de tal forma que mn = 0 mod 2 ^ | N |, e não pode ser expresso com um DFA com menos de 2 ^ | N | estados (pois pode ser necessário percorrer todos os subconjuntos de estados da NFA N).

Alexandre Passos
fonte
Isso pode ser transformado em um argumento que diz "se (alguma coisa ruim) for evitada na NFA, o DFA terá um número subexponencial de estados"?
András Salamon
11
@ András, sim. "Se o não determinismo for evitado na NFA, o DFA terá um número subexponencial de estados".
usar o seguinte comando
2
Pavel, sim, obviamente. Existe alguma propriedade não trivial que possa ser reconhecida eficientemente que também garanta uma explosão subexponencial?
András Salamon