L'automate informatique pour $L(A) / L(B)$ donne ceux pour $A,B$

Question

J'essaie de comprendre si un langage infini change la réponse.

Montrer que le langage suivant est décidable :$$L=\{\langle A,B angle : ext{$A,B$ sont des DFA, $L(B)$ est fini et $L(A)/ L(B)=L(0^*1^*)$}\}.$$

(Je parle de bonne division.)

Nous savons comment vérifier si la langue d'un DFA est finie, et étant donné deux DFA, nous savons comment vérifier si leurs langues sont égales.Les algorithmes que je connais pour les problèmes ci-dessus utilisent les DFA, il est donc nécessaire d'avoir les DFA pour résoudre ces problèmes.

J'essaie de savoir si $|L(B)|=\infty$ change la réponse.Au meilleur de ma compréhension, parce que $|L(B)|<\infty$, nous pouvons construire explicitement un DFA qui accepte $L(A)/ L(B)$, alors que si $L (B)=\infty$ tout ce que nous savons, c'est l'existence de $DFA$ qui accepte $L(A)/ L(B)$.

Cependant, même si $L(B)$ est un langage infini, puisqu'il existe un nombre fini de DFA, dont l'un accepte $L(A) / L(B)$, je peux certainement savoir qu'il existe une machine de Turing qui décide de la langue $L$.Droite?

Answer 1

Qu'est-ce que vous demandez vraiment est de savoir si un automatha A, B $ , nous pouvons construire un automate dont la langue est le quotient gauche $$ L (a) \ backslash l (b)={w: \ existe x \ in \ sigma ^ * \ text {s.t. } x \ in l (a) \ texte {et} xw \ in l (b) \}. $$ (La question a été posée entre-temps pour se référer au quotient droit, qui peut être traité de la même manière.)

Voici une telle construction. Supposons que $ a, b $ est dfas avec des états $ q_a, q_b $ , états initiaux $ q_ {0a}, q_ {0b} $ , fonctions de transition $ \ delta_a, \ delta_b $ et les états finaux $ f_a, f_b $ . Nous construisons un NFA avec des états $ q= (\ {0 \ \ \ fois q_a \ fois q_b) \ tasse (\ {1 \} \ fois q_b) $ , Etat initial $ \ LBABLE 0, Q_ {0A}, Q_ {0A} \ RANGER $ $ , Etats finaux $ \ {1 \} \ fois f_b $ et la fonction de transition suivante $ \ delta $ :

• $ \ delta (\ lambeaux 0, q_a, q_b \ ranges, \ epsilon)={\ langle 0, \ delta_a (q_a, \ sigma), \ delta_b (q_b , \ sigma) \ Rangle: \ sigma \ in \ sigma \} $ pour tous $ q_a \ in q_a \ setminus f_a $ et $ q_b \ dans q_b $ .
• $ \ delta (\ lambeaux 0, q_a, q_b \ ranges, \ epsilon)={\ langle 0, \ delta_a (q_a, \ sigma), \ delta_b (q_b , \ sigma) \ RANGER: \ sigma \ in \ sigma \ \ \ \ sigma \ \ \ tasse \ {\ langle 1, q_b \ rangs \} $ pour tous $ q_a \ in f_a $ et $ q_b \ in q_b $ .
• $ \ delta (\ langle 1, q_b \ rangs, \ sigma)={\ langle 1, \ delta_b (q_b, \ sigma) \ rangle \} $ pour tous $ \ sigma \ in \ sigma $ et $ q_b \ in q_b $

Answer 2

Cela répond à une version différente de la question, dans laquelle la langue en question est $L(A) \setmoins L(B)$.

Voici un algorithme pour décider $L$:

• Utiliser la construction du produit pour construire un DFA $CAN$ dont la langue est $L(A) \setmoins L(B)$.
• Laisser $D$ être un DFA dont la langue est $0^*1^*$.
• Utilisez à nouveau la construction du produit pour construire un DFA $E$ dont la langue est $L(C) \Delta L(D)$.
• Vérifiez (à l'aide de BFS/DFS) si un état final de $E$ est accessible depuis son état initial.
• Sortie "oui" si aucun état final n'est accessible à partir de l'état initial.Sinon, affichez "non".

Comme vous pouvez le constater, que les langages rencontrés en cours de route soient finis ou infinis ne fait absolument aucune différence pour cet algorithme.