1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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$.
$\endgroup$
5
  • $\begingroup$ thanks. I got it. There is a more general case that is still unclear to me. I suppose my question is more about whether and when there is a TM that decides the language. Lets say I would not know to find the DFA of $L(A)/L(B)$ but only know its existence. Is $L$ decidable in this case too? $\endgroup$ – Ella Jul 1 '20 at 16:11
  • $\begingroup$ You would have to be more specific. $\endgroup$ – Yuval Filmus Jul 1 '20 at 16:13
  • $\begingroup$ we use the fact that we have the DFA of $L(A)/L(B)$. a lot of times we rely on existence. Sometimes we can't find the DFA but just ensure it exists. I ask, for a hypothetical case in which we do not know how to find the DFA (Suppose you would not prove that even when $|L(B)|=\infty$, we can build NFA for $L(A)/L(B)$), but only know its existence, in this case the language was decidable? $\endgroup$ – Ella Jul 1 '20 at 17:54
  • $\begingroup$ You'll have to be more specific. It just depends on too many things. $\endgroup$ – Yuval Filmus Jul 1 '20 at 19:02
  • $\begingroup$ ok. thank you!!! $\endgroup$ – Ella Jul 1 '20 at 19:38
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I meant right division, Sorry for causing confusion :( $\endgroup$ – Ella Jul 1 '20 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.