Consider the following language $$EQ_{DFA} = \{ \langle A, B\rangle: A \ and \ B \ are \ DFAs \ and \ L(A) = L(B)\}$$

Given the fact that $EQ_{DFA}$ is decidable, how can I prove that the language $$SEQ_{DFA} = \{ \langle A, B\rangle: A \ and \ B \ are \ DFAs \ and \ L(A)\subseteq L(B)\}$$ is also decidable?

Thank you in advance

  • $\begingroup$ Hint: $L(\mathcal{A}) \subseteq L(\mathcal{B})$ iff $L(\mathcal{A}) \cap L(\mathcal{B})^C = \varnothing$. $\endgroup$ – ttnick Oct 7 '18 at 10:48
  • $\begingroup$ What does Theorem 4.5 for EQDFA say? Can you write that in the question? $\endgroup$ – Bader Abu Radi Oct 7 '18 at 11:54
  • $\begingroup$ The Theorem 4.5 proves that EQDFA is decidable using the symmetric difference $\endgroup$ – ElDon90 Oct 7 '18 at 13:00

There are several ways to prove that $SEQ_{DFA}$ is decidable. One of them is by using the fact that $EQ_{DFA}$ is decidable.

Assume that $L_1$ and $L_2$ are languages such that $L_1\leq_m L_2$ (that is, there is a mapping reduction from $L_1$ to $L_2$). It holds that if $L_2$ is decidable, then so is $L_1$. Hence, in order to prove that $SEQ_{DFA}$ is deciadable, we reduce it to $EQ_{DFA}$. As hinted in the comment, we propose the following reduction.

  • The Reduction: Let $C$ be a fixed DFA for the empty language, that is, $L(C) = \emptyset$. The reduction operates as follows. Given instance $\langle A= \langle Q_{A}, \Sigma, q^{A}_0, \delta_{A}, F_{A}\rangle, B= \langle Q_{B}, \Sigma, q^{B}_0, \delta_{B}, F_{B}\rangle\rangle$ of $SEQ_{DFA}$, the reduction computes a product automaton, $D$, for $L(A)\cap L(B)^C$ and outputs $\langle D, C\rangle$.

  • Correctness: $L(A)\subseteq L(B)$ iff $L(A)\cap L(B)^C = \emptyset$ iff $L(D) = \emptyset$ iff $L(D) = L(C)$. (the first equivalence mentioned in the comment is simple enough and thus is left for the reader).

  • Computability: the only non-trivial part is to compute $D$ given $A$ and $B$. We claim that $D$ is defined by $D = \langle Q_{A}\times Q_{B}, \Sigma, (q^{A}_0, q^{B}_0), \delta_{D}, F_{D}\rangle$. Where:

1) For every $(q, s)\in Q_{A}\times Q_{B}$ and $\sigma \in \Sigma$, $\delta_{D}$ is defined by: $$\delta_{D}((q, s),\sigma) = (\delta_{A}(q, \sigma), \delta_{B}(s, \sigma))$$

2) $F_{D} = F_{A}\times (Q_{B}\setminus F_{B})$.

Note that $D$ is a standard product automaton and thus for every finite word $w\in \Sigma^*$, we have that $\delta_{D}((q, s), w) = (\delta_{A}(q, w), \delta_{B}(s, w))$ (this can be proven by induction on $|w|$). Therefore, $w\in L(D)$ iff $\delta_{D}((q^{A}_0, q^{B}_0), w) \in F_{D}$ iff $(\delta_{A}(q^{A}_0, w),\delta_{B}(q^{B}_0, w) ) \in F_{A}\times (Q_{B}\setminus F_{B})$ iff $w\in L(A)$ and $w\in L(B)^C$ iff $w\in L(A)\cap L(B)^C$. Therefore $L(D) = L(A)\cap L(B)^C$ and thus we're done.

  • 1
    $\begingroup$ Alternatively, note that $A\subseteq B$ iff $A\cup B =B$. $\endgroup$ – Hendrik Jan Oct 7 '18 at 23:02
  • $\begingroup$ @HendrikJan Indeed, that would have been a cleaner solution :) $\endgroup$ – Bader Abu Radi Oct 8 '18 at 8:53
  • $\begingroup$ We construct a new DFA C from A and B, where C accepts only those strings that are accepted only by A or B but not only by B or both. Thus, if A is a subset of B, C will accept nothing. (using the emptiness test). $\endgroup$ – ElDon90 Jan 16 at 12:54

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.