Computing Automaton per $ L (A) / L (B) $ DAPERS per $ A, B $

Question

Sto cercando di capire se la lingua infinita cambia la risposta.

.

Mostra che la lingua seguente è decidabile: $$ L={\ Langle A, B \ Rangle: \ Text {$ A, B $ sono DFAS, $ L (B) $ è finita e $ L (A) / L (b)= l (0 ^ * 1 ^ *) $}}. $$

(Sto parlando della divisione giusta.)

Sappiamo come verificare se la lingua di un DFA è finita e data due DFA, sappiamo come controllare se le loro lingue sono uguali. Gli algoritmi che conosco i problemi di cui sopra usano il DFA, quindi è necessario avere il DFA per decidere quei problemi.

Sto cercando di capire se $ | L (B) |=INFTY $ Modifica la risposta. Al meglio della mia comprensione, perché $ | l (b) | <\ INFTY $ , possiamo costruire esplicitamente un DFA che accetta $ L (a) / l (b) $ , mentre se $ l (b)=INFTY $ Tutto ciò che sappiamo riguarda l'esistenza di $ DFA $ che accetta $ l (a) / l (b) $ .

Tuttavia, anche se $ l (b) $ è una lingua infinita, poiché c'è un numero finito di DFAS, uno dei quali accetta $ l (a) / l (b) $ , posso certamente sapere che c'è una macchina di tinger che decide la lingua $ l $ . Giusto?

Answer 1

Quello che stai davvero chiedendo è se date Automata $ A, B $ , possiamo costruire un Automaton il cui lingua è il quoziente sinistro $$ L (A) \ backslash l (b)={w: \ esiste x \ in \ sigma ^ * \ text {s.t. } x \ in l (A) \ testo {e} xw \ in l (b) \}. $$ (La domanda è al frattempo modificata per fare riferimento al quoziente destro, che può essere gestito in modo simile.)

Ecco una tale costruzione. Supponiamo che $ A, B $ sono dfas con stati $ q_a, q_b $ , dichiarazioni iniziali $ Q_ {0a}, q_ {0b} $ , funzioni di transizione $ \ delta_a, \ delta_b $ e stati finali $ f_a, f_b $ . Costruiamo un NFA con stati $ Q= (\ {0 \} \ volte Q_a \ volte Q_b) \ tazza (\ {1 \} \ volte Q_b) $ , Stato iniziale $ \ Langle 0, q_ {0a}, q_ {0b} \ Rangle $ , stati finali $ \ {1 \} \ volte f_b $ e la seguente funzione di transizione $ \ 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 \} $ per tutti $ q_a \ in q_a \ setmino f_a $ e $ 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 \ \} tazza \ \ \ langle 1, q_b \ Rangle \} $ per tutte le $ Q_a \ in f_a $ e $ q_b \ in q_b $ .
• $ \ delta (\ Langle 1, q_b \ Rangle, \ Sigma)={\ Langle 1, \ delta_b (q_b, \ sigma) \ Rangle \} $ per tutte le $ \ sigma \ in \ sigma $ e $ q_b \ in q_b $ . .

Answer 2

Questo risponde a una versione diversa della domanda, in cui la lingua in questione è $ l (a) \ setmino l (b) $ .

Ecco un algoritmo per decidere $ l $ :

.
• Utilizzare la costruzione del prodotto per costruire un DFA $ c $ la cui lingua è $ l (A) \ setmino l ( B) $ .
• Let $ D $ Be A DFA la cui lingua è $ 0 ^ * 1 ^ * $ . < / Li >.
• Utilizzare nuovamente la costruzione del prodotto per costruire una DFA $ e $ la cui lingua è $ l (c) \ delta l (D) $ .
• Verifica (utilizzando BFS / DFS) Se un po 'di stato finale di $ e $ è raggiungibile dal suo stato iniziale.
• Uscita "Sì" se nessun stato finale è raggiungibile dallo stato iniziale. Altrimenti in uscita "no".

Come puoi vedere, se le lingue incontrate lungo la strada sono finite o infinite non fanno assolutamente differenza per questo algoritmo.