Proving a Regular Expression

Question

$L$ is a language from the alphabet $\Sigma = \{a,b \}$.

Define $C(L)$ as another language. This language produces a $w$ as an element of $\{a,b\}^*$ with the property that there exists a $v \in L$ such that the number of $a$'s in $w$ is equivalent to the number of $a$'s in $v$.

I wanted to prove that if $L$ is regular, then $C(L)$ is also regular.

Note that there we are not given what L is, so the proof cannot make use of converting L into a DFA for example.

I thought of using homomorphism $h$ to change $L$ into a language that is equivalent to $C(L)$ and using the closure property that if $L$ is regular then $h(L)$ is also regular. Since $h(L)$ is equivalent to $C(L)$, we have proven the conditional.

Am I on the right track? Thanks.

Answer 1

I don’t see how you’re going to construct such a homomorphism. I would start with a DFA $M$ for $L$ and modify it to get an NFA for $C(L)$: add a $b$-transition from each state of $M$ to itself, and wherever $M$ has a transition

$$q_1\overset{b}\longrightarrow q_2\;,$$

add a transition

$$q_1\overset{\epsilon}\longrightarrow q_2\;.$$

Then show that the resulting NFA accepts $C(L)$.

Alternatively, you could start with a regular grammar $G$ for $L$ and add a new non-terminal symbol $B$. Replace each $b$ in the productions of $G$ with $B$, and add productions $B\to bB\mid\epsilon$. Then show that this modified grammar generates $C(L)$.

Answer 2

Given a word $u$, let $|u|_a$ denote the number of occurrences of $a$ in $u$. If I understood correctly, your language $C(L)$ is defined as follows: $$ C(L) = \{w \in \Sigma^* \mid \text{there exists $v \in L$ such that $|w|_a = |v|_a$}\} $$ Let $h: \Sigma^* \to a^*$ be the homomorphism defined by $h(w) = a^{|w|_a}$. I claim that $C(L) = h^{-1}(h(L))$. Indeed, $w \in h^{-1}(h(L))$ if and only if there exists $v \in L$ such that $h(w) = h(v)$, that is $|w|_a = |v|_a$. Since regular languages are closed under homomorphisms and under inverses of homomorphisms, the language $C(L)$ is regular.

Remark. The same proof would show that if $L$ is context-free, then $C(L)$ is context-free.