Proving a language comprised of 2 languages is regular

Question

So glad to find this place. I have been struggling for quite a while with this given question and i am not sure how to fully address it.

The question: $L_1$ and $L_2$ are regular languages over the same $\Sigma$. prove that the following language is regular as well:

$L^\frown \:=\left\{\:w\:\in L_1 | \:w=\sigma _1\mu _1\xi _1\sigma \:_2\mu \:_2\xi \:_2...\sigma \:_n\mu \:_n\xi \:_n\right\}$ Where $n \geq 0$, for every i:$\left(1\:\le i\:\le n:\:\sigma _i\mu _i\xi _i\:\in \Sigma \right)$, $\mu_1\mu_2...\mu_n \in L_2$.

Prove using: 1)Closure properties. 2)Building an multipication automaton

My try:

1)I do not understand how to define the homomorphism from which I can deduct using closure properties that the given language is indeed regular.

2)Since both $L_1$ and $L_2$ are regular, There exist two deterministic finite automatas that can accept them: $A^i\:=\:\left(\Sigma ,\:Q^i,q_0^i,F^i,\delta ^i\right)$ ($i\:\in \left\{\:1,2\right\})$. So, let L be the automaton that accepts those two languages: let L be $L\:=\:\left(\Sigma \:,\:Q^1\:X\:Q^2,\left(q_0^1,q_0^2\right),F^1X\:F^2,\delta \:\right)$. However, here I don't know what its transition function should be

Would really appreciate your help with it, if possible with explanations to understand so I'll be able to overcome similar questions in the future.

Thank you so much!

Answer 1

Proof using closure properties

Let $add\colon \Sigma \to \Sigma^*$ be a regular substitution that maps $\mu \in \Sigma$ to $\{ \sigma \mu \xi : \sigma, \xi \in \Sigma \}$ (the image is regular since it is finite). Then your language is $L_1 \cap add(L_2)$.

Proof using product automaton

Let $(\Sigma, Q^i, q_0^i, F^i, \delta^i)$ be automata accepting $L_i$ (for $i = 1,2$). We construct a new automaton $(\Sigma, Q, q_0, F, \delta)$ where:

• $Q = Q^1 \times Q^2 \times \{1,2,3\}$.
• $q_0 = (q_0^1,q_0^2,1)$.
• $F = F_1 \times F_2 \times \{1\}$.
• $\delta((q^1,q^2,1),\sigma) = (\delta^1(q^1,\sigma),q^2,2)$.
• $\delta((q^1,q^2,2),\sigma) = (\delta^1(q^1,\sigma),\delta^2(q^2,\sigma),3)$.
• $\delta((q^1,q^2,3),\sigma) = (\delta^1(q^1,\sigma),q^2,1)$.

The product automaton keeps track of the state in both automata, as well as the location within the triple $\sigma_i \mu_i \xi_i$ (this is the purpose of the third argument).