Computação autômato para $L(A) / L(B)$ dá para $A,$B

Question

Eu estou tentando descobrir se o infinito idioma alterar a resposta.

Mostrar que o idioma, é decidível:$$L=\{\langle A,B angle : ext{$A,$ B são DFAs, $L(B)$ é finito, e $L(A)/ L(B)=L(0^*1^*)$}\}.$$

(Estou falando de direito divisão.)

Sabemos como verificar se o idioma de um DFA é finito, e dado duas DFAs, sabemos como verificar se suas línguas são iguais.Os algoritmos eu sei que para os problemas acima usa o DFA, por isso, é necessário ter o DFA, a fim de decidir os problemas.

Eu estou tentando descobrir se $|L(B)|=\infty$ altera a resposta.Para o melhor do meu entendimento, porque $|L(B)|<\infty$, podemos explicitamente construir um DFA que aceita $L(A)/ L(B)$, enquanto se $L (B)=\infty$ tudo o que sabemos é sobre a existência de $DFA$ que aceita $L(A)/ L(B)$.

No entanto, mesmo se $L(B)$ é um infinito de linguagem, uma vez que existe um número finito de DFAs, um dos que aceita $L(A) / L(B)$, Eu certamente posso saber que existe uma máquina de Turing que decide o idioma $L$.Direito?

Answer 1

O que você está realmente perguntando é se dado autômato $ a, B $ , podemos construir um autômato cuja linguagem é o quociente esquerdo $$ L (a) \ backslash l (b)={w: \ existe x \ in \ sigma ^ * \ text {s.t. } x \ in l (a) \ text {e} xw \ em l (b) \}. $$ (A questão tem que mudou para se referir ao quociente correto, que pode ser tratado de forma semelhante.)

Aqui está uma construção. Suponha que $ a, B $ são DFAs com estados $ Q_A, Q_B $ , estados iniciais $ q_ {0a}, q_ {0b} $ , funções de transição $ \ delta_a, \ delta_b $ estados finais $ f_a, f_b $ . Construímos um NFA com estados $ q= (\ {0 \} \ vezes \ \ vezes \ thees q_b) \ cope (\ {1 \} \ vezes q_b) $ , estado inicial $ \ langer 0, q_ {0a}, q_ {0b} \ rangle $ , estados finais $ \ {1 \} \ vezes f_b $ , e a seguinte função de transição $ \ delta $ :

• $ \ delta (\ langer 0, q_a, q_b \ rangle, \ epsilon)={\ langer 0, \ delta_a (q_a, \ sigma), \ delta_b (q_b , \ sigma) \ rangle: \ sigma \ in \ sigma \ \} $ para toda $ \ \ setminus f_a $ e $ q_b \ em q_b $ .
• $ \ delta (\ langer 0, q_a, q_b \ rangle, \ epsilon)={\ langer 0, \ delta_a (q_a, \ sigma), \ delta_b (q_b , \ sigma) \ rangle: \ sigma \ in \ sigma \ \ \} \ copo {\ langle 1, q_b \ rangle \} $ para toda $ Q_A \ in F_A $ e $ q_b \ em q_b $ .
• $ \ delta (\ langer 1, q_b \ rangle, \ sigma)={\ langam 1, \ delta_b (q_b, \ sigma) \ rangle \ \ rangle \ \ rangle \ rangle Span> Para toda $ \ sigma \ in \ sigma $ e $ q_b \ em q_b $ .

Answer 2

Isso responde a uma versão diferente da questão, em que a língua em questão é $L(A) \setminus L(B)$.

Aqui está um algoritmo para decidir $L$:

• Usar o produto de construção para a construção de uma DFA $C$ cuja linguagem é $L(A) \setminus L(B)$.
• Deixe $D$ ser um DFA cuja linguagem é $0^*1^*$.
• Usar o produto de construção de novo para a construção de uma DFA $E$ cuja linguagem é $L(C) \Delta L(D)$.
• De seleção (usando BFS/DFS) se algum estado final de $E$ é acessível a partir de seu estado inicial.
• De saída "sim" se não há estado final é acessível a partir do estado inicial.Caso contrário, a saída de "não".

Como você pode ver, se as línguas encontradas ao longo do caminho são finito ou infinito não faz absolutamente nenhuma diferença para este algoritmo.