# Prove that $SEQ_{DFA}$ = {⟨A,B⟩ | A,B are DFAs and L(A) ⊆ L(B)} is decidable

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?

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

• Alternatively, note that $A\subseteq B$ iff $A\cup B =B$. – Hendrik Jan Oct 7 '18 at 23:02
• @HendrikJan Indeed, that would have been a cleaner solution :) – Bader Abu Radi Oct 8 '18 at 8:53
• 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). – ddon-90 Jan 16 '19 at 12:54