¿Diferencia entre los idiomas aceptados por dos DFA con diferentes estados iniciales / estados de aceptación?

Recientemente, hice una pregunta sobre Math SE. Ninguna respuesta todavia. Esta pregunta está relacionada con esa pregunta, pero más detalles técnicos hacia la informática.

Dados dos DFA y donde el conjunto de estados, el alfabeto de entrada y la función de transición de y son iguales, los estados iniciales y los estados finales (de aceptación) podrían ser diferentes. Permiten y sean los idiomas aceptados por y , respectivamente.B = ( Q , Σ , δ , q 2 , F 2 ) A B L 1 L 2 A $A = (Q, \Sigma, \delta, q_1, F_1)$$B = (Q, \Sigma, \delta, q_2, F_2)$$A$$B$$L_1$$L_2$$A$$B$

Hay cuatro casos:

1. F 1 = F $q_1 = q_2$ y .$F_1 = F_2$
2. F 1 = F $q_1 \neq q_2$ y .$F_1 = F_2$
3. $q_1 = q_2$ y .$F_1 \neq F_2$
4. $q_1 \neq q_2$ y .$F_1 \neq F_2$

Mi pregunta es

¿Cuáles son las diferencias entre y en los casos 2, 3 y 4?L $L_1$$L_2$

Tengo una pregunta más específica en esta línea,

El monoide de transición de un autómata es el conjunto de todas las funciones en el conjunto de estados inducidos por las cadenas de entrada. Vea la página para más detalles. El monoide de transición puede considerarse como un monoide que actúa sobre el conjunto de estados. Vea esta página Wiki para más detalles.

En muchas publicaciones, un autómata se llama fuertemente conectado cuando la acción monoide es transitiva, es decir, siempre hay al menos una transición (cadena de entrada) de un estado a otro.

Si y están conectados fuertemente autómatas, ¿cuáles son las diferencias entre y en los casos 2, 3 y 4 arriba?B L 1 L $A$$B$$L_1$$L_2$

¿Alguna literatura discutiendo estos temas en detalle?

He buscado en muchos libros y artículos y no he encontrado nada útil hasta ahora. Creo que todavía no tengo las palabras clave apropiadas. Por eso estoy buscando ayuda. Cualquier puntero / referencia será muy apreciado.

Como están fuertemente conectados, entonces si q 1 ≠ q 2 , existen palabras p 1 , p 2 tales que δ ( q 1 , p 1 ) = q 2 y δ ( q 2 , p 2 ) = q 1 .$A,B$$q_1\neq q_2$$p_1,p_2$$\delta(q_1,p_1)=q_2$$\delta(q_2,p_2)=q_1$

Considere el caso 2, luego iff p 2 w ∈ L ( B ) , y x ∈ L ( B ) iff p 1 x ∈ L ( A ) . Por lo tanto, puede agregar un prefijo para cambiar entre idiomas.$w\in L(A)$$p_2w\in L(B)$$x\in L(B)$$p_1 x\in L(A)$

Considere el caso 3, una vez más, por una fuerte conectividad a lo sumo palabras s 1 , . . . , s k tal que por cada q i ∈ F 1 tienes ese δ ( q i , s i ) ∈ F 2 , y de manera similar para la otra dirección (de B a A ).$|F_1|$$s_1,...,s_k$$q_i\in F_1$$\delta(q_i,s_i)\in F_2$$B$$A$

Por lo tanto, puede componer sufijos para cambiar entre idiomas.

Combinando estos puedes caracterizar las diferencias usando prefijos y sufijos. Por ejemplo, en el caso 4, iff p 1 w s i en L ( A ) para algunos s i en un conjunto finito predeterminado.$w\in L(B)$$p_1 w s_i$$L(A)$$s_i$

De hecho, incluso puede decir algo interesante sobre estas palabras: defina como el DFA donde q 1 es el estado inicial y q 2 es el estado final, entonces en el caso 2 tiene L ( B ) = L ( C ) ⋅ L ( A ) (y de manera similar para la otra dirección).$C$$q_1$$q_2$$L(B)=L(C)\cdot L(A)$

En cuanto a los sufijos, las cosas están más involucradas, ya que no puedes predeterminar en qué estado final terminarás. No estoy seguro de que pueda escribir esto como una concatenación, pero puede escribir donde A q es el DFA obtenido de A configurando F = { q } , y E q es un DFA que comienza en q con estados finales F 2 .$L(B)=\bigcup_{q\in F_1}L(A_q)\cdot L(E_q)$$A_q$$A$$F=\{q\}$$E_q$$q$$F_2$

Para el caso 4 puedes combinar los dos.

Puede que le preocupe que esta no sea una respuesta real, sino más bien una caracterización de propiedades utilizando palabras en lugar de estados, pero esta es una respuesta típica en este campo (de manera similar al teorema de Myhill-Nerode).