3
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ Thank you very much. If you let me know your name I will acknowledge you in the paper. $\endgroup$ Commented Jul 9, 2023 at 19:49
  • 1
    $\begingroup$ @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). $\endgroup$
    – D.W.
    Commented Jul 9, 2023 at 21:05

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.