Take the 2-minute tour ×  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!  share|improve this question
Ignore regular expressions for this. Just start with an
automaton that recognizes $L$ and c