0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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