prove or disprove if the following language is regular language

Question

for $A,B\subseteq\{0,1\}^*$ regular languages

prove or disprove that $L_2$ is a regular language:

$L_2 = \{x \in A | \exists y \in B : |x|_1 =|y|_1 \}$

$|x|_1$ means the number of appearances of 1 in the word.

if $L_2$ regular language demonstrate his automata, else disprove with pump lemma or with clousre properties.

I think $L_2$ is a regular language because I can choose $A=B$ for example and I'll get regular language or for example $B=\{0,1\}^*$.

I am not sure how to demonstrate his automata.

Answer 1

I am not entire sure if my approach work, but here we go: Firstly, we observe that we can write $L_2 = A \cap B'$ where $B' = \{s \in \Sigma^* \mid |s|_1 = |y|_1 \text{ for some } y \in B\}$. Since we can create a FSA for the intersection of two regular languages, it suffices to find a FSA for $B'$.

Before proceeding, consider a more concrete description of $B'$. Note that we can write $$B' = \{0^{\alpha_0} 1 0^{\alpha_1} 1 0^{\alpha_2} \dots 1 0^{\alpha_{|y|_1}} \mid \alpha_j \in \mathbb{N}, y \in B\}$$ Intuitively, $B'$ is constructed by taking all strings in $B$, chops away all $0$'s, and adding back any number of $0$'s in between.

Now given a FSA $M$ for $B$, we can construct a corresponding FSA $M'$ for $B'$ by the following transformation:

Case 1: should be converted to

Case 2: Nothing needs to be changed.

Case 3: should be converted to

Case 4: Nothing needs to be changed.

This completes the FSA.

Answer 2

Let $\pi: \{0,1\}^* \to 1^*$ be the monoid morphism defined by $\pi(u) = |u|_1$. Since regular languages are closed under morphisms and inverses of morphisms, $R =\pi(B)$ is regular and $L_2 = A \cap \pi^{-1}(R)$ is regular.