Como faço para verificar se um DFA é equivalente a um NFA?

10

Estou aprendendo a converter NFAs em DFAs e quero ter certeza de que estou fazendo o certo. Obviamente, voltar na outra direção não é uma coisa. Alguém conhece um algoritmo para verificar se um DFA é equivalente a um NFA?

IAmOnStackExchange
fonte
Uma interpretação do candidato: existe um "verificador de resultados" (no sentido de Wasserman e Blum ) para o problema de converter um NFA em um DFA? Em outras palavras, existe um algoritmo assintoticamente mais rápido do que a conversão propriamente dita, que, dado um suposto par (entrada, saída) para o algoritmo de conversão, verifica se a saída está correta?
DW

Respostas:

7

Esta é uma pergunta problemática. Existe uma maneira de verificar a equivalência de autômatos, o que explicarei agora, mas receio que não o ajude, como você verá no final.

Lembre-se que dois conjuntos e B são iguais se e somente se A B e B A (esta é a definição da igualdade set). Assim, basta verificar se L ( D ) L ( N ) e L ( N ) L ( D ) , onde D e N são seus DFA e NFA, respectivamente.UMABABBAL(D)L(N)L(N)L(D)DN

Mas como você verifica a contenção de idiomas, você pode perguntar. Bem, agora observar que sse Um ¯ B = (onde ¯ B é o complemento de B ).ABAB¯=B¯B

Vamos considerar primeiro verificar se . Para fazer isso, você precisa complementar D (muito fácil - troque os estados de aceitação e rejeição), construa o autômato de interseção (por exemplo, com a construção do produto) com N e verifique o vazio, encontrando o caminho para um estado de aceitação.L(N)L(D)DN

A direção inversa, no entanto, mostrará por que isso não ajuda. A fim de verificar se , você precisa complementar N . Mas, para complementar um NFA, primeiro você precisa convertê-lo em um DFA, tornando toda a ideia inútil.L(D)L(N)N

Essencialmente, o problema com sua pergunta é muito mais profundo: você deseja verificar se você (um modelo computacional indefinido) executou um algoritmo bem definido corretamente. Portanto, este não é realmente um problema de ciência da computação.

Eu direi o seguinte: seguindo as construções sugeridas, não é difícil concluir que se houver uma palavra de comprimento no máximo 2 2 n ( n sendo o número de estados de N ) que é aceito por um e não pelo outro. Assim, você pode tentar todas as palavras até esse tamanho.L(D)L(N)22nnN

Shaull
fonte
Obrigado pela resposta bem pensada. Eu aprendi algo novo hoje. Parece que minha melhor aposta é apenas comparar meu trabalho com o JFLAP.
IAmOnStackExchange
2
A menos que o seu NFA seja grande (por exemplo, com mais de 7-8 estados), sua melhor opção é provavelmente apenas verificar-se cuidadosamente. Normalmente, após a remoção de estados inacessíveis, você obtém um DFA pequeno e a verificação manual não é muito difícil.
Shaull
11
Você não pode determinar e minimizar as duas máquinas e verificar se as duas são isomórficas?
saadtaame
5

Uma maneira de proceder é converter o NFA em um DFA e depois verificar a equivalência dos dois DFAs, para os quais existe um algoritmo linear [1].

O artigo a seguir trata o caso mais geral da equivalência de duas AFNs (o que, obviamente, também se aplica ao seu caso).

Filippo Bonchi, Damien Pous, Verificando a equivalência da NFA com bisimitações até a congruência Princípio das Linguagens de Programação (POPL), janeiro de 2013, Roma, Itália. ACM, pp. 457-468, 2013.

Resumo . Introduzimos a bisimulação até a congruência como uma técnica para provar a equivalência linguística de autômatos finitos não determinísticos. Explorando essa técnica, desenvolvemos uma otimização do algoritmo clássico de Hopcroft e Karp [1]. Comparamos nossa abordagem com os algoritmos antichain introduzidos recentemente, analisando e relacionando os dois métodos subjacentes de prova coindutiva. Damos exemplos concretos em que aprimoramos exponencialmente os antichains; além disso, os resultados experimentais mostram melhorias não negligenciáveis.

[1] JE Hopcroft e RM Karp. Um algoritmo linear para testar a equivalência de autômatos finitos. TR 114, Cornell Univ., Dezembro de 1971.

Consulte também o apêndice da Web deste documento , que contém scripts de prova de Coq dos resultados, um link para uma implementação e um applet interativo.

J.-E. PIN
fonte
Uma maneira de proceder é converter o NFA em um DFA , o objetivo do pôster é verificar o resultado desse algoritmo. Aplicar duas vezes é realmente uma maneira, mas não é imune ao mal-entendido do algoritmo. Provavelmente é por isso que um método de verificação foi solicitado.
AProgrammer
2
@programmer A parte principal da minha resposta é uma referência a um algoritmo para o qual um script de prova Coq está disponível, que é certamente o método de verificação mais seguro que consigo pensar.
J.-E.
11
Não sei ao certo o que alguém não tem certeza sobre sua compreensão de um algoritmo simples como o NFA para o DFA fará com um script de prova Coq. Parece usar álgebra para resolver o problema de matemática de uma terceira série.
APROGRAMADOR #
0

essa pergunta é mais sobre teste de software aplicado e verificação da correção na prática do que uma questão teórica.

  • se você tiver outro código para cruzamentos de computação e complementos (e esvaziar línguas DFA), você pode usar a ideia de que D1 1D2¯D2D1 1¯D¯

  • você pode confiar no software testado anteriormente que foi testado para validar seus resultados. por exemplo, biblioteca AT&T FSM

  • Outra idéia: teste randomizado. escolha seqüências aleatórias no seu idioma. determine se as seqüências de caracteres são aceitas ou não pelo DFA / NFA. se os dois não forem iguais, com alta probabilidade, você encontrará seqüências que não correspondem.

  • Outra idéia: você pode escrever um código para percorrer todas as ramificações do DFA e NFA até uma profundidade específica e procurar incompatibilidades. isso é equivalente a enumerar todas as possíveis seqüências aceitas de determinados comprimentos.

vzn
fonte