$L_1$ and $L_2$ are regular languages. Is $\{ w \in L_1^{|u|} \mid u \in L_2 \}$ regular? Let $L_1$ and $L_2$ are regular languages.
Is $$L_1 ^ {|L_2|} = \{ w \in L_1^{|u|} \mid  u \in L_2 \}$$ regular?
My attempt: I think yes. I think it can be created an automaton for this $L_1 ^ {|L_2|}$ using the automata for $L_1$ and $L_2$ and maybe a cartesian product of the states.
But I can't seem to continue. Any tips?
 A: This is true even if $L_2$ is a context-free language. Indeed, the commutative image of $L_2$, that is the set
$$
\{ |u| \mid u \in L_2\}
$$
is a regular subset of $\Bbb N$, and hence a finite union of arithmetic progressions, say
$$
 \bigcup_{1 \leqslant i \leqslant k} c_i + r_i\Bbb N
$$
It follows that your language is equal to
$$
  \bigcup_{1 \leqslant i \leqslant k}L_1^{c_i}(L_1^{r_i})^*
$$
and hence is regular.
A: You're right that this language is regular. Fix DFAs $A_1$ and $A_2$ for $L_1$ and $L_2$.
Say that machine $A_i$ has states $Q_i$, with accepting states $F_i$.
Build a new (nondeterministic) machine whose states are $Q_1 \times Q_2$, as you guessed. Add transitions $(q_1, q_2) \overset{a}{\to} (q_1', q_2)$ for each $q_1 \overset{a}{\to} q_1'$.
Additionally, if $q_1 \in F_1$, we add transitions $(q_1,q_2) \overset{\epsilon}{\to} (q_1^*, q_2')$ where $q_1^*$ is the initial state of $A_1$ and $q_2 \overset{a}{\to} q_2'$ for any $a \in \Sigma$.
Obviously the initial state of this machine will be $(q_1^*, q_2^*)$ and the accepting states will be those $(q_1,q_2)$ so that $q_1 \in F_1$ and $q_2 \in F_2$.
But why does this machine work? I'll leave it to you to check the precise details, but the idea is this: We have $Q_2$ many copies of $A_1$, and every time we reach a possible end of a word in $L_1$ (since we reach an accepting state of $A_1$) we (nondeterministically) allow ourselves to start looking for a new $L_1$ word with what remains of $w$, in the copy of $A_1$ corresponding to the next letter of a word in $L_2$. If we reach a final state, it means we're at a final state in $A_1$ and in $A_2$, so that we read in a complete $L_1$ word for each letter in an $L_2$ word. That is, $w \in L_1^{|u|}$ for some $u \in L_2$.

I hope this helps ^_^
