Is this language $X = \{x:xxx\in L\}$ regular?

I came across this question in my Theory of Computation class recently:

Consider a regular language $L$, and define $X = \{x:xxx\in L\}$. Is this language regular?

I believe that it is regular, and that the procedure required to construct an NFA for it is not particularly different from constructing one for $W=\{x:xx\in L\}$ (at the very least, the one I will now attempt to do).

This is mostly a hunch, but I was thinking something like this:

Consider an NFA $A = (Q, \Sigma, \delta, s, F)$ that accepts $L$. Let's try to see what kind of words will pass through $A$ twice before being accepted. It's quite easy to see that the ones for which this works are those words which follow a path

$$s\rightarrow^{x}q\rightarrow^x f$$

Where $s$ is the start state, $f$ is an accept state and $q$ is some state in the middle (which we don't know about). Just to keep things simple, we make sure that there is only one start state and final state; we can do that, in any case, by adding $\epsilon$ arrows.

Pick some $q\in Q$. Doesn't matter which.

Now let's form a new NFA $A'$ whose states are $Q\times Q$, and put $(s,q)$ as the only start state, and $(q,f)$ as the only accept state. The transition function will be

$$\delta'((a,b),x) = (\delta(a,x),\delta(b,x))$$

The only elements that will be accepted here are those for which there's a run from $s\rightarrow q$ and $q\rightarrow f$.

Now we have no way of knowing whether the 'midway point' of $xx$ while going through $A$ is indeed the state $q$. However, because of nondeterminism, we don't need to guess - we can make one copy of this for each state $q$. Then my hypothesis is that the accepted words of the union of all these NFAs are those which are doubly accepted by $A$.

Caveats: I'm quite certain that my constructed NFA will accept $W$, but my problem is that I believe that it will likely accept other inputs as well. Secondly, I'm sure that this solution generalizes to the original problem as well, but I'm having a hard time

• Yes. What you are constructing is the product automaton recognizing the language $L_{s,q}\cap L_{q,f}$, where for $q, q' \in Q$, $L_{q,q'}$ is the language of words leading from state $q$ to state $q'$. Formally:

$$L_{q,q'} = \{u\in \Sigma^\mid q'\in \delta^(q, u)\}$$
It is well known that $L_{q,q'}$ is a regular language (just consider the initial state $q$ and the final state $q'$ with the same transitions in $A$).

• The same idea can be used: $X = \bigcup\limits_{q,q'\in Q} L_{s,q}\cap L_{q,q'}\cap L_{q',f}$.

StackExchange Computer Science Q#145780, answer score: 4