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?
computability
automata
finite-automata
decision-problem
Richard Jones
fuente
fuente
Respuestas:
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,A2 AΔ 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Δ)
fuente
Dados dos DFA y , la igualdad de y y verificar si y generan el mismo lenguaje son las mismas cosas.D1 D2 D1 D2 D1 D2
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.D1 D2
fuente