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)}$?


1 Answer 1


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.

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

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.