prova geral de equivalência de dois FSMs em tempo finito?

Question

Será que a exist geral prova para a equivalência de dois (determinísticos) máquinas de estados finitos que sempre leva tempo finito? Isto é, dado dois FSMs, você pode provar que, dadas as mesmas entradas eles sempre produzem os mesmos resultados sem realmente precisar para executar as FSMs (que poderia ser não-terminação?). Se tal prova um existe, o que é a complexidade de tempo?

Answer 1

Não é uma prova, embora eu não sei isso. Procure livro de Sipser sobre o assunto, que é onde eu conheço-lo partir.

scrounging minha memória: basicamente, não há um único DFA mínimo para um determinado DFA, e não há um algoritmo de minimização que sempre termina. Minimizar ambos A e B, e ver se eles têm o mesmo DFA mínimo. Eu não sei a complexidade do minimização, que não é muito ruim (eu acho que é polinomial). Gráfico isomorfismo é muito difícil de calcular, mas porque há um nodo especial começando, pode espero ser um pouco mais fácil. Você não pode mesmo exigir gráfico isomorfismo, para ser honesto.

Mas não, você não precisar realmente executar o DFAs, basta analisar a sua estrutura.

Answer 2

Suponha que você tenha dois FSMs com O ( n ) estados. Então você pode fazer um FSM de tamanho O ( n ² ) que reconhece apenas a diferença simétrica de seus aceitam idiomas. (Adicione um FSM que tem estados que correspondem a um par de estados, um de cada FSM. Em seguida, em cada etapa, atualizar cada parte do par simultaneamente. Um estado no novo FSM é um estado aceito sse exatamente um do par era um estado aceitar.) Agora minimizar este FSM e ver se é o mesmo que o FSM trivial de um estado que rejeita tudo. Minimizando uma FSM com m estados leva tempo O ( m log m ), de modo geral você pode fazer tudo no tempo O ( n ² log n ).

@Agor afirma corretamente que Sipser é uma boa referência para esses tipos de coisas. O ponto-chave da minha resposta é que você pode fazer isso em tempo polinomial, mesmo com uma pequena expoente.