Quais são as condições para um NFA para seu DFA equivalente ter tamanho máximo?

24

Sabemos que os DFAs são equivalentes aos NFAs em poder de expressividade; também existe um algoritmo conhecido para converter NFAs em DFAs (infelizmente agora conheço o inventor desse algoritmo), o que, na pior das hipóteses, nos dá estados, se nosso NFA tivesse estados. S2SS

Minha pergunta é: o que está determinando o pior cenário possível?


Aqui está uma transcrição de um algoritmo em caso de ambiguidade:

Seja um NFA. Construímos um DFA em queA = ( Q , Σ , δ , q 0 , F )UMA=(Q,Σ,δ,q0 0,F)UMA=(Q,Σ,δ,q0 0,F)

  • Q=P(Q) ,
  • F={SQ|FS} ,
  • δ(S,uma)=sS(δ(s,uma)δ^(s,ε)) e
  • q0 0={q0 0}δ^(q0 0,ε) ,

onde é a função de transição alargada de .δ^UMA

Daniil
fonte
como os comentários indicam, você pode resgatar esse Q solicitando um NFA "mínimo" para um DFA (um problema em aberto). sempre pensei que este problema estivesse intimamente ligado à questão P =? NP de várias maneiras e tenha algumas formulações semelhantes que sugerem isso. é semelhante porque você está perguntando sobre DFAs "compressíveis" vs "incompressíveis", onde "incompressível" é o pior caso, de modo que a NFA mínima seja quase do tamanho do DFA. provavelmente há algum teorema como, "a maioria dos DFAs, tomadas ao acaso, são incompressíveis [em NFAs]", pois há thms semelhantes em teoria da informação re Kolmogorov complexidade das cordas etc.
vzn

Respostas:

24

O algoritmo a que você se refere é chamado de Construção Powerset e foi publicado pela primeira vez por Michael Rabin e Dana Scott em 1959.

Para responder sua pergunta como indicado no título, não há DFA máximo para um idioma normal, pois você sempre pode fazer um DFA e adicionar quantos estados desejar com as transições entre eles, mas sem transições entre um dos estados originais e um dos novos. Assim, os novos estados não será acessível a partir do estado inicial , então a linguagem aceita pelo autômato não vai mudar (desde δ ( q 0 , w ) permanecerá o mesmo para todos w Σ * ).q0δ^(q0,w)wΣ

Dito isso, é claro que não pode haver condições em um NFA para que seu DFA equivalente seja o máximo, uma vez que não existe um DFA equivalente exclusivo . Por outro lado, o DFA mínimo é único até o isomorfismo.


Um exemplo canônico de um idioma aceito por uma NFA com estados com DFA equivalente a 2 n estados é L = { w { 0 , 1 } : | w | n  e o  n- ésimo símbolo do último é 1 } . Um NFA para G é Um = Q , { 0 , 1 } , δ , q 0 , {n+12n

L={w{0,1}:|w|n and the n-th symbol from the last one is 1}.
L , com δ ( q 0 , 0 ) = { q 0 } , δ ( q 0 , 1 ) = { q 0 , q 1 } e δ ( q i , 0 ) = δ ( q i , 1 ) = { q i + 1 } para iUMA=Q,{0 0,1},δ,q0 0,{qn+1}δ(q0 0,0 0)={q0 0}δ(q0 0,1)={q0 0,q1}δ(qEu,0 0)=δ(qEu,1)={qEu+1} . O DFA resultante da aplicação da construção powerset a esta NFA terá 2 n estados, porque você precisa para representar todos os 2 n palavras de comprimento n como sufixos de uma palavra em L .Eu{1,...,n}2n2nneu
Janoma
fonte
A propósito, se você quiser que os colchetes apareçam no modo matemático da tela, use \\ {e \\}.
Zach Langley #
@ZachLangley Eu já tentei, ele não funciona :-(
Janoma
Parece estar funcionando para mim na pré-visualização. Não posso enviar a edição, porque estou adicionando apenas quatro caracteres e o mínimo é seis. Você está usando duas barras invertidas e não funcionou?
Zach Langley
@ZachLangley Ele funciona agora, mas duas coisas: 1º, não funcionou quando publiquei a resposta pela primeira vez. Segundo, acho que isso é inconsistente com o comportamento da renderização do LaTeX na história, mas posso estar errado.
Janoma
O DFA resultante é mínimo? Você poderia falar um pouco sobre como provar que é mínimo?
user834
8

O pior caso de vem do número de subconjuntos de estados da NFA. Para que o algoritmo do teorema de Kleene forneça um DFA equivalente com o pior número de estados, deve haver uma maneira de chegar a todos os subconjuntos possíveis de estados no NFA. Um exemplo com dois estados sobre o alfabeto { a , b } possui uma transição do estado inicial para o único estado de aceitação no símbolo a , uma transição do estado de aceitação de volta para a inicial em b e uma transição do estado de aceitação de volta para em um a ou b . As strings λ , a , b2s{uma,b}umabumabλumab, e levam aos subconjuntos { q 1 } , { q 2 } , { } e { q 1 , q 2 } , respectivamente, e esses precisam de estados separados no DFA que Kleene fornece.umab{q1}{q2}{}{q1,q2}

Patrick87
fonte
concordou, mas a questão de "se existe uma maneira de obter a cada subconjunto possível de estados da NFA" não é trivial e vale a pena um estudo mais aprofundado ....
vzn
-1

Eu acredito que essa é uma questão na fronteira do conhecimento, ou seja, basicamente uma questão de pesquisa. A partir de uma rápida pesquisa no Google, parece estar quase sempre aberta. Além disso, por muitos anos eu acreditei que fosse importante e vinculado aos limites inferiores da teoria da complexidade. Você não menciona diretamente uma análise estatística, mas é isso que está implícito na sua pergunta. Aqui estão dois exemplos de estudos estatísticos sobre DFAs / NFAs que são semelhantes para mostrar a abordagem geral de perguntas desse tipo. Parece que a pesquisa empírica básica sobre questões como essa ainda é quase inexplorada. É certo que o segundo não está diretamente relacionado à sua pergunta, mas é o mais próximo que pude encontrar da pesquisa atual.

x

Essa métrica estaria relacionada a métricas da teoria dos grafos, como densidade de arestas, etc. Provavelmente, existe alguma métrica muito importante da teoria dos grafos ou uma mistura de métricas que estima a "explosão", mas isso não é imediatamente óbvio para mim. Eu poderia sugerir algo como métricas de coloração de gráfico ou métricas de clique, talvez. Em seguida, teste a métrica em relação aos dois conjuntos "blow-up" vs "not blow-up".

Até agora, outras respostas à sua pergunta fornecem apenas um exemplo de caso de "explosão" (útil para um estudo de caso), mas não abordam a questão principal de uma métrica geral.

Outra área para analisar um programa de pesquisa empírica desenvolvido com sucesso é a pesquisa de pontos de transição do SAT. Isso desenvolveu vínculos muito profundos com os conceitos de física e termodinâmica. Parece-me provável que conceitos semelhantes sejam aplicáveis ​​aqui. Por exemplo, é provável que você encontre métricas de tipo de ponto de transição análogas; provavelmente densidade de arestas etc. Observe paralelos à teoria da compressibilidade de Kolmogorov.

Suponho também que os NFAs que "explodem" em comparação com aqueles que não o fazem são, de alguma forma, muito análogos a instâncias "difíceis" vs "fáceis" de problemas de NP-completos.

Outra maneira de estudar esse problema seria formular um problema de minimização da NFA. Ou seja, dado um DFA, encontre o NFA mínimo, que ouvi pela última vez (muitos anos atrás), ainda era um problema em aberto.


[1] Sobre o desempenho de algoritmos de minimização de autômatos Marco Almeida, Nelma Moreira, Rogério Reis

[2] Autômatos que não reconhecem palavras: uma abordagem estatística Cristian S. Calude, Cezar Câmpeanu, Monica Dumitrescu

vzn
fonte