Como provar que os DFAs dos NFAs podem ter um número exponencial de estados?

20

Todos os autômatos finitos não determinísticos podem ser transformados em autômatos finitos determinísticos equivalentes. No entanto, um autômato finito determinístico permite apenas uma única seta por símbolo apontando de um estado. Portanto, seus estados devem ser membros do conjunto de estados da NFA. Isso parece indicar que o número de estados do DFA poderia escalar exponencialmente em termos do número de estados do NFA. No entanto, eu queria saber como realmente provar isso.

John Hoffman
fonte
7
É uma pergunta razoável, e a construção não é completamente óbvia, mas ainda pode ser uma pergunta de lição de casa. Portanto, seria útil saber por que você quer saber.
há algumas construções aqui, mas parece que deveria estar em um papel em algum lugar. não sei de uma ref. também fora da minha cabeça acho que existe uma construção tal que a NFA conta em binário em seus estados ativos e aceita somente após cerca de transições ...? 2n
vzn
Veja também cs.stackexchange.com/questions/3381/…
Gilles 'SO- stop

Respostas:

15

Uma operação que transforma um NFA em outro NFA, mas não o faz para um DFA, é a reversão (aponte todas as setas ao contrário e troque os estados iniciais pelos estados de aceitação). O idioma reconhecido pelo autômato transformado é o idioma invertido .LR={un1u0u0un1L}

Assim, uma idéia é procurar uma linguagem que tenha uma construção assimétrica. No futuro, esse idioma deve ser reconhecido inspecionando os primeiros símbolos, exigindo apenas n + O ( 1 ) estados. Retrocedendo, deve ser necessário manter uma memória dos últimos n estados, o que requer A n + O ( 1 ) estados em que A é o tamanho do alfabeto.nn+O(1)nAn+O(1)A

Estamos procurando um idioma com a forma que M n consiste em palavras de comprimento n , S é um subconjunto não trivial do alfabeto e M ' não fornece mais restrições. Podemos também escolher o alfabeto mais simples A = { a , b } (um alfabeto singleton não funciona, não há NFAs menores lá) e M = A . Um S não trivial significa S = { a } . Quanto aMnSMMnnSMA={a,b}M=ASS={a} , exigimos que ele não se correlacione com S (para que o DFA do idioma invertido precise manter a memória de S ): use M n = A n .MnSSMn=An

Assim, seja . É reconhecido por um DFA simples com n + 2 estados.Ln=(a|b)na(a|b)n+2

dfa

A reversão produz um NFA que reconhece .LnR=(a|b)a(a|b)n

nfa

O DFA mínimo que reconhece tem pelo menos 2 n + 1 estados. Isso ocorre porque todas as palavras de comprimento 2 n + 1 devem atingir estados distintos no DFA. (Em outras palavras, eles pertencem a classes distintas de equivalência Myhill-Nerode .) Para provar isso, use duas palavras distintas u , v A n + 1 e deixe k ser uma posição em que diferem ( u kv k ). Sem perda de generalidade, vamos supor que u kLnR2n+12n+1u,vAn+1kukvk e v k = b . Então u b kL R n e v b kL R n ( b k é uma extensão distintiva para u e v ). Se u e v levassem ao mesmo estado em um DFA reconhecendo L R n , então u b k e v b kuk=avk=bubkLnRvbkLnRbkuvuvLnRubkvbk, o que é impossível, pois um leva a um estado de aceitação e o outro não.

Agradecimento: este exemplo foi citado na Wikipedia sem explicações. O artigo faz uma referência a um artigo que eu não li que fornece um limite maior:
Leiss, Ernst (1981), "Representação sucinta de linguagens regulares por autômatos booleanos", Theoretical Computer Science 13 (3): 323-330, doi: 10.1016 / S0304-3975 (81) 80005-9 .

Gilles 'SO- parar de ser mau'
fonte
nQQ2nn2n
1
n2nnn 2n2n1
hmm ... depois de ler sua resposta duas vezes e do comentário "Mas aqui queremos ver que o limite é alcançado" agora eu poderia entender. Obrigado.
Grijesh Chauhan
8

Ln={x1,x2,,xk#xk+1:i{1,,k} with xi=xk+1}

Ln{#,1,,n}

O(n)Lnnii3

Ln2O(n){1,,n}

Tenho certeza de que o livro de Sipser tem esse exemplo.

Cara
fonte
A construção no livro de Siper produz um DFA com exatamente 2 ^ n estados. Se o NFA possui o conjunto de estados Q, então o conjunto de estados do DFA é Pow (Q) para simular todos os possíveis estados 'paralelos' em que uma migração de NFA deve estar. (Edite para adicionar opinião sobre o escopo da pergunta) Se a construção usada para isso em um texto padrão mostra claramente a possibilidade de um número exponencial de estados, parece-me que esse não é o nível de pesquisa. Pode ser adequado como um pedido de referência.
Logan Mayfield
8

nn2n

Este exemplo também mostra que os NFAs podem sofrer uma explosão exponencial por complementação. De fato, sabe-se que qualquer NFA (ou mesmo gramática livre de contexto) para o idioma de todas as palavras que contêm todos os símbolos do alfabeto deve ter um número exponencial de estados.

Yuval Filmus
fonte
1
σΣ(Σσ)
ΣnO(n2)2n2n
O ponto deste exemplo é que a explosão corresponde exatamente à construção do conjunto de potência. Existe um exemplo binário com a mesma explosão, mas é mais complicado.
Yuval Filmus
Sim, é um bom exemplo.
6005
1
O(nlogn)