3
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ 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)$." $\endgroup$ – Eugen Oct 31 '18 at 8:41
  • 1
    $\begingroup$ Beautiful proof! $\endgroup$ – Apass.Jack Oct 31 '18 at 8:45
  • $\begingroup$ @Eugen $q$ is an arbitrary state. It is the argument to $f$ or $g$. $\endgroup$ – Yuval Filmus Oct 31 '18 at 8:51
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Adnan Oct 31 '18 at 14:32
  • $\begingroup$ @Adnan I don't get your point. What are $y_1$ and $y_2$ and what is $x$? $\endgroup$ – xskxzr Oct 31 '18 at 15:14
  • $\begingroup$ 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$. $\endgroup$ – Adnan Oct 31 '18 at 15:18
  • $\begingroup$ @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$? $\endgroup$ – xskxzr Oct 31 '18 at 18:45
  • $\begingroup$ No doubts, just trying to present an example to conform my understanding of the method. $\endgroup$ – Adnan Nov 4 '18 at 20:32
-2
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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\}^*$. $\endgroup$ – Hendrik Jan Oct 31 '18 at 1:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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