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?
  • $\begingroup$ 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). $\endgroup$
    – Nathaniel
    Nov 15, 2021 at 18:17

1 Answer 1

  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}$.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.