$L_1$ and $L_2$ are regular languages. Is $\{ w \in L_1^{|u|} \mid u \in L_2 \}$ regular?

Question

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?

Answer 1

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 ^_^

Answer 2

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.