I've got a question that asks me to explain how if a language L is regular, then so is:
$M=\{s \in \{a, b\}^* |\ \exists\ t \in L\ such\ that\ |s|_a = |t|_a\}$
I believe I would have to get M into the form: $M=\{a^i |\ i\geq0\}$ since we know that any equation of that form is regular, but I'm not quite sure how to go about that using closure properties.
Here are several possible ways of proving that if $L$ is regular then so is $M$.
Method 1
Show first that the language $K = \{ a^r : |s|_a=r \text{ for some } s \in M \}$. You can obtain $K$ from $L$ by deleting all letters other than $a$. Then show that $M$ is regular by "undeleting" all letters other than $a$.
Method 2
Construct an NFA for $M$ directly, given an NFA for $L$. At each step, the new NFA accepts non-$a$ letters gratuitously, both in the input and in its simulation of the NFA for $L$. It also reads $a$, but then must also simulate an $a$ transition on the NFA for $L$. Finally, it accepts whenever it can get the NFA for $L$ to be at an accepting state.
Method 3
Parikh's theorem shows that $K$ (defined in Method 1) is eventually periodic. That is, for some integers $m,p$ and sets $A \subseteq \{0,\ldots,m\}$, $B \subseteq \{0,\ldots,r-1\}$ we have $$ K = \{ a^i : i \in A \} \cup \{ a^{m+rj+i} : j \geq 0, i \in B \}. $$ Given this, we can construct a DFA for $M$ directly (exercise).
