# prove or disprove if the following language is regular language

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.

• Are $A$ and $B$ regular languages? Also, I assume prove that "$L_2$ is a formal language" is a typo, since this would be trivial and doesn't match the title. Should it say "regular language"? – Joey Kilpatrick Nov 25 '18 at 4:02
• @JoeyKilpatrick you are right, edited. – UltimateMath Nov 25 '18 at 7:43
• Let $B' = \{s \in \Sigma^* \mid |s|_1 = |y|_1 \text{ for some } y \in B\}$, then $L_2 = A \cap B'$, can you find an automatum for $B'$? – Alex Vong Nov 25 '18 at 8:01

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.

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.