# 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 giving an explicit construction.

1. Does this work?
2. Does this also give a construction for $$X$$? If so, what is it explicitly?
• It would be more rigorous to write $\delta'((a, b), x) = \delta(a, x) \times \delta(b, x)$, since $\delta(a, x)$ is a set of states and not a state (given that $A$ is a NFA). Nov 15, 2021 at 18:17

1. 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$$).
2. The same idea can be used: $$X = \bigcup\limits_{q,q'\in Q} L_{s,q}\cap L_{q,q'}\cap L_{q',f}$$.