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

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.

• $y^0, y^1, y^2,...$ is countable (and infinite if $y$ is not the empty word.) – Apass.Jack Oct 30 '18 at 22:07

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

• In both these sentences, it is unclear what $q$ is: "The idea is that the DFA is at state f after reading a word w if $\delta(q,w)=f(q)$. When at state $f$ and reading $\sigma$, we move to the state $g$ given by $g(q) =\delta(f(q),\sigma)$." – Eugen Oct 31 '18 at 8:41
• Beautiful proof! – Apass.Jack Oct 31 '18 at 8:45
• @Eugen $q$ is an arbitrary state. It is the argument to $f$ or $g$. – Yuval Filmus Oct 31 '18 at 8:51

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

• For $L_1$, if I take $A$ as $0^* 1$ and suppose $y_1=001, y_2=0001$, then is it correct to say $y_1=(001)^1 \rightarrow x=001$, and $y_2=(0001)^1 \rightarrow x=0001$? – Adnan Oct 31 '18 at 14:32
• @Adnan I don't get your point. What are $y_1$ and $y_2$ and what is $x$? – xskxzr Oct 31 '18 at 15:14
• I'm assuming $A$ as $0^* 1$, $y_1$ and $y_2$ are strings of $A$, and $x$ is the string derived as given mapping for $L_1$. – Adnan Oct 31 '18 at 15:18
• @Adnan If I understand you correctly, that's yes, of course. But I don't know why you ask such a question, do you have any doubt about the definition of $L_1$? – xskxzr Oct 31 '18 at 18:45
• No doubts, just trying to present an example to conform my understanding of the method. – Adnan Nov 4 '18 at 20:32

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^*)$$.

• That would mean that $L_2$ is equal to $A^*$, and I do not think that is correct. $L_2$ considers powers of the same word. If $A=\{a,b\}$ then $L_2 = a^*+b^*$ which differs from $\{a,b\}^*$. – Hendrik Jan Oct 31 '18 at 1:10