Suppose $A$ and $B$ are both languages over $\Sigma=\{0,1\}$. We use $n_0(x)$ and $n_1(x)$ to represent the number of $0$s and $1$s in the string $x$ respectively. Consider the following two operations: $$ A\cong_0 B=\{x\in A\mid\exists y\in B,\ \text{s.t. }n_0(x)=n_0(y)\}\\ A\cong_{01} B=\{x\in A\mid\exists y\in B,\ \text{s.t. }n_0(x)=n_0(y)\wedge n_1(x)=n_1(y)\} $$ How to prove that the class of regular languages is closed under $\cong_0$ operation and not closed under $\cong_{01}$ operation?
1 Answer
For $A\cong_0 B$, consider $\mathcal{A}_A$ and $\mathcal{A}_B$ two automata that recognize $A$ and $B$ respectively. Construct $\mathcal{A}'_B$ where you replace $1$-transitions in $\mathcal{A}_B$ with $\varepsilon$-transitions and add a $1$-transition loop on each state. Now, the product automaton between $\mathcal{A}_A$ and $\mathcal{A}'_B$ should recognize $A\cong_0 B$.
For $A\cong_{01}B$, consider $A = a^*b^*$ and $B = (ab)^*$. Both are regular languages, however, $A\cong_{01}B = \{a^nb^n\mid n\in \mathbb{N}\}$ which is a well known non-regular language.