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?

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.

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.

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.

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).