Existe uma maneira de testar se dois NFAs aceitam o mesmo idioma?

10

Ou pelo menos gere um conjunto de strings que um NFA aceite, para que eu possa alimentá-lo no outro NFA. Se eu fizer uma pesquisa em todos os caminhos da NFA, isso funcionará? Embora isso demore muito tempo.

algorithms regular-languages finite-automata Duncan
fonte
Não (pelo menos não é do nosso conhecimento). A igualdade da NFA é completa no PSPACE. Veja esta discussão .
Shaull
@ Shaull: O OP não fez uma maneira eficiente .
frafl
@rafraf: Você está certo. Presumi que "levará muito tempo" que o OP quer uma solução eficiente. Ainda assim, meu comentário menciona que está no PSPACE, então é decidível.
Shaull

Respostas:

10

O problema de decisão está completo no PSPACE, como observou Shaull.

Contudo, na prática, muitas vezes é possível decidir a equivalência de NFA razoavelmente rapidamente. Mayr e Clemente (com base em evidências experimentais) afirmam que a complexidade do caso médio escala quadraticamente . Suas técnicas dependem da remoção do sistema de transição rotulado subjacente por meio de aproximações locais de inclusões de traços.

Assim como o SAT é NP-completo em uma análise de pior caso, mas muitas vezes resulta surpreendentemente tratável para instâncias do mundo real, parece provável que a equivalência de NFA pode ser decidida com eficiência para muitas instâncias do mundo real.

András Salamon
fonte