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$
1
  • 2
    $\begingroup$ $y^0, y^1, y^2,...$ is countable (and infinite if $y$ is not the empty word.) $\endgroup$
    – John L.
    Oct 30, 2018 at 22:07

3 Answers 3

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$
3
  • $\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, 2018 at 8:41
  • 1
    $\begingroup$ Beautiful proof! $\endgroup$
    – John L.
    Oct 31, 2018 at 8:45
  • $\begingroup$ @Eugen $q$ is an arbitrary state. It is the argument to $f$ or $g$. $\endgroup$ Oct 31, 2018 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$
5
  • $\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, 2018 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, 2018 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, 2018 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, 2018 at 18:45
  • $\begingroup$ No doubts, just trying to present an example to conform my understanding of the method. $\endgroup$
    – Adnan
    Nov 4, 2018 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$
1
  • 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$ Oct 31, 2018 at 1:10

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.