Given a language $L$, define the language $K$ as the language $L$ where every second character is replaced with a $\#$. (Note: $\#$ is not part of the alphabet of $L$.) For example, if $L = \{ab, aabb, abbab \}$, then $K = \{a\#, a\#b\#, a\#b\#b \}$.
How can I prove that if $L$ is regular, then $K$ is also regular?
I think that I should transform the regular expression that defines $L$ to a series of sub-NDFA's and change the sub-NDFA's according to what operation is used ($*$, $|$ or $\cup$).
But that gives me the problem that I don't know if the previous sub-NDFA will have produced a string of odd or even length when arriving at the current sub-NDFA.
Example: If you have '$aa^{\ast} a$' you would have 3 sub-NDFA's ($a$, $a^{\ast}$ and $a$), but how can I know if I would have to change the last NDFA to $\#$ instead of leaving it at "$a$"?
All help is welcome!