# Use NFA to express the left quotient of the language of a DFA with respect to the language of another DFA

Let $$\Sigma = \{a,b\}$$, $$L_1,L_2\subseteq \Sigma^*.$$

$$L_1 \triangleleft L_2 = \{w\in \Sigma^* \mid \exists v\in L_1, vw \in L_2\}$$

For clarity, here is python code that shows $$L_3 \triangleleft L_4$$:

answer = set()
L3 = {"aa", "b", "bb"}
L4 = {"a", "b", "ab", "bb", "aaa", "bbab"}
for c in L3:
for c1 in L4:
if c1.startswith(c):
# output: {'', 'a', 'ab', 'b', 'bab'}


$$\mathcal{L(A_1)}$$ means the language accepted by DFA $$\mathcal{A_1}$$.

Let $$\mathcal{A_1} = \{Q_1, \Sigma, \delta_1,q_{1,0},F_1\}$$, $$\mathcal{A_2}= \{Q_2, \Sigma, \delta_2,q_{2,0},F_2\}$$ be 2 DFAs, how to write an NFA to accept $$\mathcal{L(A_1)}\triangleleft\mathcal{L(A_2)}$$?

#### An NFA with $$\epsilon$$-moves

Here is an NFA with $$\epsilon$$-moves $$\mathcal M=((Q_1\times Q_2)\sqcup Q_2, \Sigma, \delta, (q_{1,0},q_{2,0}), F_2)$$, where $$\delta$$ is defined as below.
$$\quad\delta((r,s), \epsilon)=\{(\delta_1(r, \sigma), \delta_2(s, \sigma))\mid \sigma\in\Sigma\}\quad\forall r\in Q_1\setminus F_1,\, \forall s\in Q_2$$,
$$\quad\delta((r,s), \epsilon)=\{(\delta_1(r, \sigma), \delta_2(s, \sigma))\mid \sigma\in\Sigma\}\sqcup\{s\}\quad\forall r\in F_1,\, \forall s\in Q_2$$,
$$\quad\delta(s,\sigma)=\{\delta_2(s,\sigma)\}\quad\forall s\in Q_2,\ \forall\sigma\in\Sigma.$$

In plain words, upon an input word $$w$$, $$\mathcal M$$ will simulate $$\mathcal A_1$$ and $$\mathcal A_2$$ in parallel, as if both DFAs are given the same arbitrary input. When the simulation of $$\mathcal A_1$$ goes into one of its final states, $$\mathcal M$$ will optionally switch to continue the simulation of $$\mathcal A_2$$ only and with input $$w$$. $$\mathcal M$$ accepts when the lonely simulation of $$\mathcal A_2$$ ends up at one of its final states.

We can prove that $$\mathcal M$$ accepts $$\mathcal{L(A_1)}◃\mathcal{L(A_2)}$$ routinely.

#### Also as an NFA

Because of the equivalence of NFA with $$\epsilon$$-moves to NFA, the construction above can be transformed methodically to build an equivalent NFA, which is what is wanted in the question.

#### What if $$\mathcal L(\mathcal A_1)$$ is replaced by any language?

In fact, we can build an NFA with $$\epsilon$$-moves for $$\mathcal D\triangleleft \mathcal L(\mathcal A_2) = \{w\in \Sigma^* \mid \exists v\in {\mathcal D},\ vw \in\mathcal L(\mathcal A_2)\}$$ where $$\mathcal D$$ is any language, i.e., it can be non-regular or even non-computable.

Assume $$\mathcal D$$ is nonempty. Let $$Q_{\mathcal D}=\{\delta(q_{2,0}, v)\in Q_2\mid v\in {\mathcal D}\}$$.
Define $$\mathcal N=(Q\sqcup\{q_{\text{new}}\}, \Sigma, \mu, q_{\text{new}}, F_2)$$, where $$\mu$$ is defined below.
$$\quad\mu(q_{\text{new}}, \epsilon)=Q_{\mathcal D}$$
$$\quad\mu(q, \sigma)=\{\delta(q, \sigma)\}\quad\forall q\in Q, \forall\sigma\in\Sigma$$

Thanks to $$Q_{\mathcal D}$$, $$\mathcal N$$ looks even simpler than $$\mathcal M$$.

We have $$\mathcal L(\mathcal N)={\mathcal D}\triangleleft {\mathcal L}(\mathcal A_2)$$. In particular, the right-hand side is a regular language.

• Is there redundant brackets? $((\delta_1(r, \sigma), \delta_2(s, \sigma))$ or $(\delta_1(r, \sigma), \delta_2(s, \sigma))$ ? Apr 21, 2022 at 10:56
• @AsukaMinato Thanks. Updated. Apr 21, 2022 at 11:10