Computing automaton for $L(A) / L(B)$ gives ones for $A,B$

Question

I'm trying to figure out whether infinite language change the answer.

Show that the following language is decidable: $$L=\{\langle A,B \rangle : \text{$A,B$ are DFAs, $L(B)$ is finite, and $L(A)/ L(B)=L(0^*1^*)$}\}.$$

(I am talking about right division.)

We know how to check whether the language of a DFA is finite, and given two DFAs, we know how to check whether their languages are equal. The algorithms I know to the above problems uses the DFA's, so it is necessary having the DFA's in order to decide those problems.

I'm trying to figure out whether $|L(B)|=\infty$ changes the answer. To the best of my understanding, because $|L(B)|<\infty$, we can explicitly construct a DFA that accepts $L(A)/ L(B)$, whereas if $L (B)=\infty$ all we know is about the existence of $DFA$ that accepts $L(A)/ L(B)$.

However, even if $L(B)$ is an infinite language, since there is a finite number of DFAs, one of which accepts $L(A) / L(B)$, I can certainly know that there is a Turing machine that decides the language $L$. Right?

Answer 1

What you are really asking is whether given automata $A,B$, we can construct an automaton whose language is the left quotient $$ L(A) \backslash L(B) = \{ w : \exists x \in \Sigma^* \text{ s.t. } x \in L(A) \text{ and } xw \in L(B) \}. $$ (The question has meanwhile changed to refer to right quotient, which can be handled similarly.)

Here is such a construction. Suppose that $A,B$ are DFAs with states $Q_A,Q_B$, initial states $q_{0A},q_{0B}$, transition functions $\delta_A,\delta_B$, and final states $F_A,F_B$. We construct an NFA with states $Q = (\{0\} \times Q_A \times Q_B) \cup (\{1\} \times Q_B)$, initial state $\langle 0, q_{0A}, q_{0B} \rangle$, final states $\{1\} \times F_B$, and the following transition function $\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 \}$ for all $q_A \in Q_A \setminus F_A$ and $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 \} \cup \{ \langle 1, q_B \rangle \}$ for all $q_A \in F_A$ and $q_B \in Q_B$.
• $\delta(\langle 1, q_B \rangle, \sigma) = \{ \langle 1, \delta_B(q_B, \sigma) \rangle \}$ for all $\sigma \in \Sigma$ and $q_B \in Q_B$.

Answer 2

This answers a different version of the question, in which the language in question is $L(A) \setminus L(B)$.

Here is an algorithm for deciding $L$:

• Use the product construction to construct a DFA $C$ whose language is $L(A) \setminus L(B)$.
• Let $D$ be a DFA whose language is $0^*1^*$.
• Use the product construction again to construct a DFA $E$ whose language is $L(C) \Delta L(D)$.
• Check (using BFS/DFS) whether some final state of $E$ is reachable from its initial state.
• Output "yes" if no final state is reachable from the initial state. Otherwise output "no".

As you can see, whether the languages encountered along the way are finite or infinite makes absolutely no difference for this algorithm.