El autómata informático para $L(A) / L(B)$ da unos para $A,B$

Question

Estoy tratando de averiguar si el lenguaje infinito cambia la respuesta.

Demuestre que el siguiente lenguaje es decidible:$$L=\{\langle A,B angle : ext{$A,B$ son DFA, $L(B)$ es finito y $L(A)/ L(B)=L(0^*1^*)$}\}.$$

(Estoy hablando de la división correcta).

Sabemos cómo comprobar si el lenguaje de un DFA es finito y, dados dos DFA, sabemos cómo comprobar si sus lenguajes son iguales.Los algoritmos que conozco para los problemas anteriores utilizan DFA, por lo que es necesario tener DFA para poder decidir esos problemas.

Estoy tratando de averiguar si $|L(B)|=\infty$ cambia la respuesta.A mi leal saber y entender, porque $|L(B)|<\infty$, podemos construir explícitamente un DFA que acepte $L(A)/ L(B)$, mientras que si $L (B)=\infty$ todo lo que sabemos es sobre la existencia de $DFA$ que acepta $L(A)/ L(B)$.

Sin embargo, incluso si $L(B)$ es un lenguaje infinito, ya que hay un número finito de DFA, uno de los cuales acepta $L(A) / L(B)$, ciertamente puedo saber que hay una máquina de Turing que decide el idioma $l$.¿Bien?

Answer 1

Lo que realmente estás preguntando es si los autómatas dados $A,B$, podemos construir un autómata cuyo lenguaje sea el cociente izquierdo$$ l (a) back -savlash l (b) = {w:\existe x \en \Sigma^* ext{ s.t.} x \en L(A) ext{ y } xw \en L(B) \}.$$(Mientras tanto, la pregunta ha cambiado para referirse al cociente correcto, que se puede manejar de manera similar).

Aquí hay tal construcción.Suponer que $A,B$ son DFA con estados $Q_A,Q_B$, estados iniciales $q_{0A},q_{0B}$, funciones de transición $\delta_A,\delta_B$, y estados finales $F_A,F_B$.Construimos una NFA con estados $Q = (\{0\} imes Q_A imes Q_B) \cup (\{1\} imes Q_B)$, estado inicial $\langle 0, q_{0A}, q_{0B} angle$, estados finales $\{1\} \veces F_B$, y la siguiente función de transición $\delta$:

• $\delta(\langle 0, q_A, q_B angle, \epsilon) = \{ \langle 0, \delta_A(q_A,\sigma), \delta_B(q_B,\sigma) angle :\sigma \en \Sigma \}$ para todos $q_A \en Q_A \setminus F_A$ y $q_B \en Q_B$.
• $\delta(\langle 0, q_A, q_B angle, \epsilon) = \{ \langle 0, \delta_A(q_A,\sigma), \delta_B(q_B,\sigma) angle :\sigma \in \Sigma \} \cup \{ \langle 1, q_B angle \}$ para todos $q_A \en F_A$ y $q_B \en Q_B$.
• $\delta(\langle 1, q_B angle, \sigma) = \{ \langle 1, \delta_B(q_B, \sigma) angle \}$ para todos $\sigma \en \Sigma$ y $q_B \en Q_B$.

Answer 2

Esto responde a una versión diferente de la pregunta, en la que el idioma en cuestión es $ l (a) \ setminus l (b) $ .

Aquí hay un algoritmo para decidir $ l $ :

• Usa la construcción del producto para construir un DFA $ C $ cuyo idioma es $ l (a) \ setminus l ( B) $ .
• Let $ d $ Sé un DFA cuyo idioma es $ 0 ^ * 1 ^ * $ . < / li>
• Use la construcción del producto nuevamente para construir un DFA $ E $ cuyo idioma es $ l (c) \ delta l (D) $ .
• Check (usando BFS / DFS) Si un estado final de $ e $ se puede llegar desde su estado inicial.
• Salida "Sí" Si no se puede llegar al estado final desde el estado inicial. De lo contrario, salida "no".

Como puede ver, si los idiomas encontrados en el camino son finitos o infinitos no tienen ninguna diferencia para este algoritmo.