MHB Show Closure of Regular Languages: $L_1$ and $L_2$

[mathmari]

Hey!

How can we show that the class of regular languages is closed under the following operation??

Let $L_1$ and $L_2$ be laguages over $\Sigma=\{0, 1\}$.

The operation is: $$\{x \in L_1 | \text{ for some } y \in L_2, \text{ strings } x \text{ and } y \text{ contains equal numbers of } 1s \}$$

(Wondering)

Is the only way to show this to create a NFA of the new language?? (Wondering)

 

[mathmari]

Let $M_{L_1}=(Q_{L_1},\Sigma ,\delta_{L_1},q_{L_1},F_{L_1})$ the DFA that recognizes $L_1$ and $M_{L_2}=(Q_{L_2},\Sigma ,\delta_{L_2},q_{L_2},F_{L_2})$ the DFA that recognizes $.L_2$. Let $M=(Q,\Sigma ,\delta,q,F)$ the NFA that recognizes the operation. $Q=Q_{L_1}\times Q_{L_2}, q=(q_{L_1},q_{L_2})$. Is this correct?? Which is the Transition function??

 

[mathmari]

When we "see" the number $1$ at $x \in L_1$, then we go to the next symbol of $y \in L_2$ to check if it also $1$.

Is this correct? What would be the general formula for the transition function?

 

[Evgeny.Makarov]

Let $f(x)$ be the function that erases all 0s from the word $x$. The result of your operation on $L_1$ and $L_2$ can be expressed as $L_1\cap\{x\mid f(x)\in f[L_2]\}$. But $f(x)\in f[L_2]\iff x\in f^{-1}[f[L_2]]$. Now, $f$ is a homomorphism, and regular languages are closed under homomorphic images and inverse images (Google it).

 

[mathmari]

Let $f(x)$ be the function that erases all 0s from the word $x$. The result of your operation on $L_1$ and $L_2$ can be expressed as $L_1\cap\{x\mid f(x)\in f[L_2]\}$. But $f(x)\in f[L_2]\iff x\in f^{-1}[f[L_2]]$. Now, $f$ is a homomorphism, and regular languages are closed under homomorphic images and inverse images (Google it).

Is this, using an homomorphism, the only way to show it? (Wondering)

 

[mathmari]

I found in my book the following description of $M$:

• $Q=Q_{L_1} \times Q_{L_2}$
  
• for each $(q, r) \in Q$ and $\Sigma$, $\delta$ is defined as followed $$\delta \left (\left (q, r\right ), a\right )=\left\{\begin{matrix}
  \{(\delta_{L_1}(q,0),r)\} & \text{ if } a=0\\
  \{(\delta_{L_1}(q,1),\delta_{L_2}(r,1))\} & \text{ if } a=1\\
  \{(q,\delta_{L_2}(r,0))\} & \text{ if } a=\varepsilon
  \end{matrix}\right.$$
  
• $q_0=(q_{L_1}, q_{L_2})$, and
  
• $F=F_{L_1} \times F_{L_2}$

Could you explain to me the transition function $\delta$ ? (Wondering)

 

[Evgeny.Makarov]

Could you explain to me the transition function $\delta$ ?

Are you familiar with the construction of the automaton that accepts the intersection of two languages? It's from the proof that regular languages are closed under intersection. In fact, there are two proofs: one uses closure under union and De Morgan's law, and the other provides a direct construction. I am talking about the latter.