# What is the solution of this equation on regular languages?

I need to characterize this language:

$$L = \{ s \in \Sigma^* \, | \, \{s\} \cdot A_1 \subseteq B_1 \land \ldots \land \{s\} \cdot A_n \subseteq B_n \}$$ where $$A_i, B_i$$ are all regular languages. My question is whether $$L$$ is regular or not, and in the positive case how we can construct a regular expression (or an automaton) for it in terms of those for the $$A_i, B_i$$. I don't even know where to start. Can anyone give me a suggestion, or point me to any literature that may help me in the task?

$$L$$ is regular. I'll prove this for $$n=1$$; then it follows for arbitrary $$n$$, as the intersection of regular languages is itself regular.

Define

$$L = \{x \in \Sigma^* \mid \{x\} \cdot A \subseteq B\}.$$

I will construct a finite-state automaton $$M_L$$ for $$L$$, proving that $$L$$ is regular.

Let $$M_A,M_B$$ be deterministic finite-state automata for the languages $$A,B$$. WLOG we can assume they have no useless or unreachable states. Let $$s_0,t_0$$ denote the start states for $$M_A,M_B$$.

$$M_L$$'s states have the form $$\langle s,t \rangle$$ or $$\langle \bot,t \rangle$$, where $$s,t$$ range over states of $$M_A,M_B$$, respectively.

$$M_L$$ has a transition $$\langle s,t \rangle \stackrel{c}{\to} \langle s',t' \rangle$$ if $$M_A$$ has a transition $$s \stackrel{c}{\to} s'$$ and $$M_B$$ has a transition $$t \stackrel{c}{\to} t'$$. Also, $$M_L$$ has a transition $$\langle \bot,t \rangle \stackrel{\epsilon}{\to} \langle s_0,t \rangle$$ for each $$t$$.

Mark the state $$\langle s_0,t \rangle$$ as accepting in $$M_L$$ iff for every path $$\langle s_0,t \rangle \leadsto \langle s',t' \rangle$$ in $$M_L$$ such that $$s'$$ is accepting in $$M_A$$, $$t'$$ is accepting in $$M_B$$. (*)

You should be able to prove that $$M_L$$ forms a finite-state automaton for $$L$$. I'll let you work out the details of the proof. If you want, you can easily adjust $$M_L$$ to be deterministic by removing the few $$\epsilon$$ transitions. This gives you the result you desired, as well as a constructive algorithm to form an automaton recognizing the language. Combine this with the standard method (product automaton) for the intersection of multiple regular languages, and you obtain a solution for arbitrary $$n$$ as well.

Footnote (*): Also, you can efficiently find all such states using a single depth-first search. Let

$$I = \{\langle s',t' \rangle \mid s' \text{ is accepting}, t' \text{ is not accepting}\}.$$

Now do a depth-first search backwards through $$M_L$$, starting from the set of states $$I$$ defined as follows, to find all states $$R$$ that are reachable (going backwards) from $$I$$. Mark every state of the form $$\langle s_0,t\rangle$$ that is not in $$R$$ as accepting in $$M_L$$; all other states of $$M_L$$ are not accepting.

• Thank you very much. If you let me know your name I will acknowledge you in the paper. Jul 9 at 19:49
• @PietroBraione, you're welcome. No need, but I appreciate the offer. Please do check the details here carefully in case I have made a mistake (I make many mistakes).
– D.W.
Jul 9 at 21:05