Is the power of a regular language regular? Is the root of a regular language regular?

Question

If $A$ is a regular set, then:

$L_1=\{x\mid\exists n \geq0, \exists y \in A: y=x^n\}$,

$L_2=\{x\mid \exists n \geq0, \exists y\in A: x=y^n\}$.

Which one of them is regular?

My reasoning is since in $L_2$ we can have uncountable $x$ from even one value of $y\ (y^0, y^1, y^2,...),\ L_2$ cannot be regular. But that thinking seems wrong.

Answer 1

The language $L_2$ is not necessarily regular. Indeed, consider $A = a^*b$. If $L_2$ were regular, then so would the following language be: $$L_2 \cap a^*ba^*b = \{ a^nba^nb : n \geq 0 \}.$$ However, this language is not regular (exercise).

In contrast, the language $L_1$ is regular. We can see this by constructing a DFA for it. Let the DFA for $L_1$ have states $Q$, initial state $q_0$, accepting states $F$, and transition function $\delta$. The states of the new DFA are labeled by functions $Q \to Q$. The idea is that the new DFA is at state $f\colon Q \to Q$ if the original DFA moves from state $q \in Q$ to state $f(q)$ after reading $w$ (i.e., if $\delta(q,w) = f(q)$ for all $q \in Q$). The initial state is the identity function. When at state $f$ and reading $\sigma$, we move to the state $g$ given by $g(q) = \delta(f(q),\sigma)$. A state is accepting if $f^{(n)}(q_0) \in F$ for some $n \geq 0$.

Answer 2

$L_1$ is regular.

Let $M=(Q,\Sigma,\delta,q_0,F)$ be a DFA recognizing $A$, and we denote by $M(s)$ the state $M$ reaches finally after reading the string $s$. Consider some $x\in L_1$, and let $n$ be the smallest one such that $M$ accepts $x^n$. We have $M(x^n)\in F$, and $M(x^0),M(x^1),\ldots,M(x^{n-1})\notin F$ (otherwise we can choose a smaller $n$ instead). Moreover, $M(x^0),M(x^1),\ldots,M(x^{n-1})$ must be pairwise different otherwise $M$ will never reach $M(x^n)$, hence we have $n\le |Q|$. This means we can rewrite $L_1$ as

$$L_1=\bigcup_{n=0}^{|Q|}\{x\mid x^n\in A\}.$$

We only need to prove $\{x\mid x^n\in A\}$ is regular for all $n$ because the union of finite many regular languages is still a regular language. We prove this claim by mathematical induction.

For $n=0,1$, this is trivial.

Suppose $\{x\mid x^n\in A\}$ is regular for some $n\ge 1$. Denote by $M_q=(Q,\Sigma,\delta,q,F)$, i.e. the DFA by changing the start state of $M$ to $q$. We have \begin{align} \{x\mid x^{n+1}\in A\}&=\bigcup_{q\in Q}\{x\mid M(x)=q \wedge M_q(x^{n})\in F\}\\ &=\bigcup_{q\in Q}\left(\{x\mid M(x)=q \}\cap\{x\mid M_q(x^{n})\in F\}\right). \end{align} Since $\{x\mid M(x)=q \}$ and $\{x\mid M_q(x^{n})\in F\}$ (by inductive assumption) are both regular languages for all $q\in Q$, $\{x\mid x^{n+1}\in A\}$ is also a regular language.

Q.E.D.

---

$L_2$ is not regular.

Let $A$ be the language expressed by the regular expression $0^*1$, then $L_2$ is not regular by pumping lemma.

Answer 3

I used the following reasoning, but it has a flaw, see comment below:

$L_2$ is regular. As $A$ is regular, then there is a regular expression $e$ such that $A=L(e)$. It is easy to see that $L_2=L(e^*)$.