<p><span class="math-container">$L$</span> is regular.  I'll prove this for <span class="math-container">$n=1$</span>; then it follows for arbitrary <span class="math-container">$n$</span>, as the intersection of regular languages is itself regular.</p>
<p>Define</p>
<p><span class="math-container">$$L = \{x \in \Sigma^* \mid \{x\} \cdot A \subseteq B\}.$$</span></p>
<p>I will construct a finite-state automaton <span class="math-container">$M_L$</span> for <span class="math-container">$L$</span>, proving that <span class="math-container">$L$</span> is regular.</p>
<p>Let <span class="math-container">$M_A,M_B$</span> be deterministic finite-state automata for the languages <span class="math-container">$A,B$</span>.  WLOG we can assume they have no useless or unreachable states.  Let <span class="math-container">$s_0,t_0$</span> denote the start states for <span class="math-container">$M_A,M_B$</span>.</p>
<p><span class="math-container">$M_L$</span>'s states have the form  <span class="math-container">$\langle s,t \rangle$</span> or <span class="math-container">$\langle \bot,t \rangle$</span>, where <span class="math-container">$s,t$</span> range over states of <span class="math-container">$M_A,M_B$</span>, respectively.</p>
<p><span class="math-container">$M_L$</span> has a transition <span class="math-container">$\langle s,t \rangle \stackrel{c}{\to} \langle s',t' \rangle$</span> if <span class="math-container">$M_A$</span> has a transition <span class="math-container">$s \stackrel{c}{\to} s'$</span> and <span class="math-container">$M_B$</span> has a transition  <span class="math-container">$t \stackrel{c}{\to} t'$</span>.  Also, <span class="math-container">$M_L$</span> has a transition <span class="math-container">$\langle \bot,t \rangle \stackrel{\epsilon}{\to} \langle s_0,t \rangle$</span> for each <span class="math-container">$t$</span>.</p>
<p>Mark the state <span class="math-container">$\langle s_0,t \rangle $</span> as accepting in <span class="math-container">$M_L$</span> iff for every path <span class="math-container">$\langle s_0,t \rangle \leadsto \langle s',t' \rangle$</span> in <span class="math-container">$M_L$</span> such that <span class="math-container">$s'$</span> is accepting in <span class="math-container">$M_A$</span>, <span class="math-container">$t'$</span> is accepting in <span class="math-container">$M_B$</span>. (*)</p>
<p>You should be able to prove that <span class="math-container">$M_L$</span> forms a finite-state automaton for <span class="math-container">$L$</span>.  I'll let you work out the details of the proof.  If you want, you can easily adjust <span class="math-container">$M_L$</span> to be deterministic by removing the few <span class="math-container">$\epsilon$</span> 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 <span class="math-container">$n$</span> as well.</p>
<hr />
<p>Footnote (*): Also, you can efficiently find all such states using a single depth-first search.  Let</p>
<p><span class="math-container">$$I = \{\langle s',t' \rangle \mid s' \text{ is accepting}, t' \text{ is not accepting}\}.$$</span></p>
<p>Now do a depth-first search backwards through <span class="math-container">$M_L$</span>, starting from the set of states <span class="math-container">$I$</span> defined as follows, to find all states <span class="math-container">$R$</span> that are reachable (going backwards) from <span class="math-container">$I$</span>.  Mark every state of the form <span class="math-container">$\langle s_0,t\rangle$</span> that is not in <span class="math-container">$R$</span> as accepting in <span class="math-container">$M_L$</span>; all other states of <span class="math-container">$M_L$</span> are not accepting.</p>

CC BY-SA 4.0
2023-07-09T19:49:37.360Z
Thank you very much. If you let me know your name I will acknowledge you in the paper.
Pietro Braione
CC BY-SA 4.0
2023-07-09T21:05:42.520Z
@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.
CC BY-SA 4.0
2023-07-09T02:49:32.207Z
2023-07-09T21:07:44.207Z
2023-07-09T21:07:44.207Z
D.W.
<p>I need to characterize this language:</p>
<p><span class="math-container">$$
L = \{ s \in \Sigma^* \, | \, \{s\} \cdot A_1 \subseteq B_1 \land \ldots \land \{s\} \cdot A_n \subseteq B_n \}
$$</span>
where <span class="math-container">$A_i, B_i$</span> are all regular languages. My question is whether <span class="math-container">$L$</span> 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 <span class="math-container">$A_i, B_i$</span>. 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?</p>

<fl.formal-languages><regular-language>
What is the solution of this equation on regular languages?
Pietro Braione
# What is the solution of this equation on regular languages?

(Asked by: username_0 on 2023-07-08)

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?

**Tags:** fl.formal-languages, regular-language


---

## 1 answers

### Answer by username_1 on 2023-07-09. Score: 3 | Accepted answer

$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.

> **Comments:**
> **username_0**: Thank you very much. If you let me know your name I will acknowledge you in the paper.  
> **username_1**: @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).  

---

