¿Es la igualdad de dos DFA un problema decidible?

11

Entonces, dados dos DFA, ¿es el problema de encontrar si generan el mismo idioma un problema decidible?

Ya sé que la igualdad de dos CFL no es decidible

pero ¿qué pasa con la igualdad de dos DFA? Teniendo en cuenta que la mayoría de los problemas con los DFA son decidibles, ¿esto también es decidible?

Richard Jones
fuente
1
Sí, es decidible en tiempo lineal drona.csa.iisc.ernet.in/~deepakd/atc-common/…
abc
1
Bienvenido a la informática! Que has intentado ¿Dónde te quedaste atascado? No queremos simplemente darle la solución; Queremos que entiendas. Sin embargo, dado que no sabemos cuál es su problema subyacente, no podemos comenzar a ayudarlo. Consulte aquí para obtener consejos sobre cómo hacer preguntas sobre problemas de ejercicio. Si no está seguro de cómo mejorar su pregunta, ¿por qué no preguntar en Computer Science Chat ?
Raphael

Respuestas:

22

Para decidir si los idiomas generados por dos DFA A_1 por el mismo, construya un DFA para la diferencia simétrica , y verifique si .A1,A2AΔL(A1)ΔL(A2):=(L(A1)L(A2))(L(A2)L(A1))L(AΔ)=

Aquí hay algunos detalles más. Puede construir usando la construcción del producto : construya un autómata del producto y use como el conjunto de estados de aceptación.AΔ(F1×F2¯)(F1¯×F2)

Para verificar si está vacío o no, es suficiente verificar si se puede alcanzar algún estado de aceptación desde el estado inicial, y esto puede hacerse usando BFS / DFS.L(AΔ)

Yuval Filmus
fuente
3

Dados dos DFA y , la igualdad de y y verificar si y generan el mismo lenguaje son las mismas cosas.D1D2D1D2D1D2

Sí, este problema es decidible. Puede minimizar tanto y y comparar sus funciones de transición. Dado un DFA, el algoritmo de minimización reduce el número de estados a un número mínimo y este DFA es único. Aquí hay un enfoque alternativo.D1D2

fade2black
fuente
1
Creo que estás combinando la "equivalencia" de los DFA y su igualdad.
einpoklum
@einpoklum sí, uso el término "igualdad" como sinónimo de "equivalencia" porque el OP usa el término "Igualdad".
fade2black
2
Sin embargo, los dos no son lo mismo. Incluso después de la minimización, los autómatas no son iguales . Sin embargo, sabemos que son isomórficos, lo que ciertamente es decidible (si es potencialmente más difícil que la igualdad).
Raphael