Let $L$ be a regular language over $\Sigma$. Show that: $$\left\{ x_1x_2 \dotsm x_k \mid x_1,x_2,\ldots , x_k \in \Sigma, \exists y_1, y_2, \ldots, y_k \in \Sigma: x_1y_1\dotsm x_ky_k \in L \right\}$$ is also a regular language.
I'd be glad for help. By the way, at class we showed that a regular language is closed under "Character Removing" operation. Could it be utilized here?
Think in terms of the DFA accepting $L$. If you know the theorem that NFAs and DFAs are equivalent (their sets of accepted languages are both just the set of regular languages), you can construct an NFA by first applying the initial DFA transition from the start state as usual given $x_1$, and then having empty string transitions to all $| \Sigma |$ possibilities for $y_1$, and then from these states apply the transition for $x_2$, etc. When you apply the transition for $x_j$ (i.e. your target string in $L$ has odd length, ending with an $x_j$ instead of a $y_j$) you should make sure this is not to an accept state in the NFA. The NFA states corresponding to empty string transitions based on $y_j$ should either be accept or reject depending on what the original DFA's state is after the particular value of $y_j$ is chosen.
It is clear that an NFA can handle empty string transitions because the transition function from a state is to a subset of states, and given an empty string transition you can just add all the target states of empty string transitions to the subset of states obtained when transitioning from the state before the empty string transitions. I used empty string transitions just for clarity.