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 Answers 2

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
    Commented Jul 1, 2020 at 16:11
  • $\begingroup$ You would have to be more specific. $\endgroup$ Commented Jul 1, 2020 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
    Commented Jul 1, 2020 at 17:54
  • $\begingroup$ You'll have to be more specific. It just depends on too many things. $\endgroup$ Commented Jul 1, 2020 at 19:02
  • $\begingroup$ ok. thank you!!! $\endgroup$
    – Ella
    Commented Jul 1, 2020 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
    Commented Jul 1, 2020 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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