Computer-Automaton für $ l (a) / l (b) $ gibt einen für $ A, B $

Question

Ich versuche herauszufinden, ob unendliche Sprache die Antwort ändert.

Zeigen Sie, dass die folgende Sprache entschieden ist: $$ L={\ Langle A, B \ Rangle: \ Text {$ A, B $ sind DFAS, $ l (B) $ ist endlich und $ l (a) / L (b)= l (0 ^ * 1 ^ *) $} \}. $$

(ich spreche von der rechten Division.)

Wir wissen, wie man prüft, ob die Sprache eines DFA endlich ist, und zwei DFAs, wissen wir, ob ihre Sprachen gleich sind. Die Algorithmen, die ich für die obigen Probleme kenne, verwendet die DFAs, daher ist es notwendig, die DFAs zu haben, um diese Probleme zu entscheiden.

Ich versuche herauszufinden, ob $ | L (B) |=inmTy $ ändert die Antwort. Nach bestem meines Verständnisses, weil $ | L (b) | <\ Infty $ , können wir explizit ein DFA erstellen, das $ L (a) / l (b) $ , während $ l (b)=infty $ alles, was wir wissen, über die Existenz von $ dfa $ , die $ l (a) / l (b) $ akzeptiert.

jedoch, auch wenn $ l (b) $ eine unendliche Sprache ist, da es eine endliche Anzahl von DFAs gibt, von denen eine $ l (a) / l (b) $ , ich kann sicher wissen, dass es eine Turing-Maschine gibt, die die Sprache $ L $ entscheidet . Richtig?

Answer 1

Was Sie wirklich fragen, ist, ob Automata $ A, B $ , wir können einen Automaton erstellen, dessen Sprache der linke Quotient ist $$ L (a) \ backslash l (b)={w: \ existiert x \ in \ sigma ^ * \ text {s.t. } x \ in l (a) \ text {und} xw \ in l (b) \}. $$ (Die Frage hat inzwischen geändert, um sich auf den richtigen Quotienten zu verweisen, der ähnlich gehandhabt werden kann.)

Hier ist eine solche Konstruktion. Angenommen, der $ A, B $ sind DFAS mit Status $ q_a, q_b $ , ursprüngliche Zustände $ q_ {0a}, q_ {0b} $ , Übergangsfunktionen $ \ DELTA_A, \ DELTA_B $ und endgültige Zustände $ F_A, F_B $ . Wir erstellen einen NFA mit Status $ q= (\ {{0 \ \ \ \ times q_a \ times q_b) \ cup (\ {1 \ \ \ \ \ times q_b) $ , Anfangszustand $ \ Langle 0, q_ {0a}, q_ {0b} \ Rangle $ , Endstatus $ \ {1 \ \ \ \ mal f_b $ , und die folgende Übergangsfunktion $ \ Delta $ :

.
• $ \ DELTA (\ Langle 0, q_a, q_b \ Rangle, \ Epsilon)={\ langle 0, \ delta_a (q_a, \ sigma), \ delta_b (q_b , \ sigma) \ rangle: \ sigma \ in \ sigma \} $ für alle $ q_a \ in q_a \ setminus f_a $ und $ q_b \ in q_b $ .
• $ \ DELTA (\ Langle 0, q_a, q_b \ Rangle, \ Epsilon)={\ langle 0, \ delta_a (q_a, \ sigma), \ delta_b (q_b , \ SIGMA) \ Rangle: \ Sigma \ in \ Sigma \ \ \ Sigma \ \ \ Sigma 1, q_b \ Rangle \} $ für alle $ q_a \ in f_a $ und $ q_b \ in q_b $ .
• $ \ DELTA (\ Langle 1, q_b \ Rangle, \ Sigma)={\ Langle 1, \ DELTA_B (Q_B, \ Sigma) \ Rangla \} $ für alle $ \ sigma \ in \ sigma $ und $ q_b \ in q_b $ .

Answer 2

Dies beantwortet eine andere Version der Frage, in der die fragliche Sprache $ l (a) \ setminus l (b) $ ist.

Hier ist ein Algorithmus zum Entscheiden von $ L $ :

.
• Verwenden Sie die Produktkonstruktion, um einen DFA $ C $ zu erstellen, dessen Sprache $ l (a) \ setminus l ( B) $ .
• let $ D $ Seien Sie ein DFA, dessen Sprache $ 0 ^ * 1 ^ * $ ist. < / li>
• Verwenden Sie die Produktkonstruktion erneut, um einen DFA $ E $ zu erstellen, dessen Sprache $ l (c) \ Delta l ist (D) $ .
• Prüfen (mit BFS / DFS), ob ein Endzustand von $ E $ von seinem ursprünglichen Zustand erreichbar ist.
• Ausgabe "Ja", wenn kein Endzustand aus dem ursprünglichen Zustand erreichbar ist. Ansonsten Ausgabe "Nein".

Wie Sie sehen, ob die auf dem Weg besuchten Sprachen endlich oder unendlich sind, macht für diesen Algorithmus absolut keinen Unterschied.