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.

  • $\begingroup$ 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"? $\endgroup$ – Joey Kilpatrick Nov 25 '18 at 4:02
  • $\begingroup$ @JoeyKilpatrick you are right, edited. $\endgroup$ – UltimateMath Nov 25 '18 at 7:43
  • $\begingroup$ 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'$? $\endgroup$ – 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: B case 1 should be converted to B' case 1

Case 2: B case 2 Nothing needs to be changed.

Case 3: B case 3 should be converted to B' case 3

Case 4: B 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.