Return to Question

Let $A$ be a regular set. Consider the two sets below.

\begin{align*} L_1 &= \{ x \mid \exists{n}\geq 0 , \exists{y} \in A : y =x^{n} \}, \\ L_2 &= \{ x \mid \exists{n}\geq 0 , \exists{y} \in A : x =y^{n} \}. \end{align*}

Which of the following is true?

1. $L_1$ and $L_2$ are regular
2. $L_1$ is regular but $L_2$ is not
3. $L_2$ is regular but $L_1$ is not
4. Both are not regular

What I know

$Y \in A $ only but now the relation between $y$ and $x$ is: $Y = X^{n}$ and given the clause there exist associated with the value of $n$, so we can assign any value of $n$ which is $\geq 0$. So if $n = 1$, then $Y = X$ and hence $X$ is obviously regular set.

Similarly on setting $n = 2$, we get $Y = X^{2}$ meaning $Y$ can be partitioned on exactly 2 halves and hence we can say $X$ is $\mathrm{half}(Y)$. And we know given a language or a set $L$ is regular, then $\mathrm{half}(L)$ is also regular.

With this understanding I came to a conclusion that $L_1$ is regular.

But, How to check the regularity of $L_2$? I also wanted to confirm my approach to $L_1$ being regular is correct.

Let $A$ be a regular set. Consider the two sets below.

\begin{align*} L_1 &= \{ x \mid \exists{n}\geq 0 , \exists{y} \in A : y =x^{n} \}, \\ L_2 &= \{ x \mid \exists{n}\geq 0 , \exists{y} \in A : x =y^{n} \}. \end{align*}

Which of the following is true?

1. $L_1$ and $L_2$ are regular
2. $L_1$ is regular but $L_2$ is not
3. $L_2$ is regular but $L_1$ is not
4. Both are not regular

What I knew

$Y \in A $ only but now the relation between $y$ and $x$ is: $Y = X^{n}$ and given the clause there exist associated with the value of $n$, so we can assign any value of $n$ which is $\geq 0$. So if $n = 1$, then $Y = X$ and hence $X$ is obviously regular set.

Similarly on setting $n = 2$, we get $Y = X^{2}$ meaning $Y$ can be partitioned on exactly 2 halves and hence we can say $X$ is $\mathrm{half}(Y)$. And we know given a language or a set $L$ is regular, then $\mathrm{half}(L)$ is also regular.

With this understanding I came to a conclusion that $L_1$ is regular.

But, How to check the regularity of $L_2$? I also wanted to confirm my approach to $L_1$ being regular is correct.

Let A be a regular set. Consider the two sets below.

L1 = {$x \mid \exists{n}\geq 0 , \exists{y} \in A : y =x^{n}$}

L2 = {$x \mid \exists{n}\geq 0 , \exists{y} \in A : x =y^{n}$}

Which of the following is True?

1. L1 and L2 are Regular
2. L1 is Regular but Not L2
3. L2 is Regular but Not L1
4. Both are not Regular

What I know

$Y \in A $ only but now the relation between Y and X is: $Y = X^{n}$ and given the clause there exist associated with the value of $n$, so we can assign any value of n which is $>= 0$. So if $n = 1$, then $Y = X$ and hence $X$ is obviously regular set.

Similarly on setting $n = 2$, we get $Y = X^{2}$ meaning Y can be partitioned on exactly 2 halves and hence we can say X is half(Y). And we know given a language or a set L is regular, then half(L) is also regular.

With this understanding I came to a conclusion that L1 is Regular .

But, How to check the Regularity for L2 ? I also wanted to confirm my approach to L1 being Regular is correct  .

Let $A$ be a regular set. Consider the two sets below.

\begin{align*} L_1 &= \{ x \mid \exists{n}\geq 0 , \exists{y} \in A : y =x^{n} \}, \\ L_2 &= \{ x \mid \exists{n}\geq 0 , \exists{y} \in A : x =y^{n} \}. \end{align*}

Which of the following is true?

1. $L_1$ and $L_2$ are regular
2. $L_1$ is regular but $L_2$ is not
3. $L_2$ is regular but $L_1$ is not
4. Both are not regular

What I know

$Y \in A $ only but now the relation between $y$ and $x$ is: $Y = X^{n}$ and given the clause there exist associated with the value of $n$, so we can assign any value of $n$ which is $\geq 0$. So if $n = 1$, then $Y = X$ and hence $X$ is obviously regular set.

Similarly on setting $n = 2$, we get $Y = X^{2}$ meaning $Y$ can be partitioned on exactly 2 halves and hence we can say $X$ is $\mathrm{half}(Y)$. And we know given a language or a set $L$ is regular, then $\mathrm{half}(L)$ is also regular.

With this understanding I came to a conclusion that $L_1$ is regular.

But, How to check the regularity of $L_2$? I also wanted to confirm my approach to $L_1$ being regular is correct.

Let A be a regular set. Consider the two sets below.

L1 = {$x \mid \exists{n}\geq 0 , \exists{y} \in A : y =x^{n}$}

L2 = {$x \mid \exists{n}\geq 0 , \exists{y} \in A : x =y^{n}$}

Which of the following is True?

1. L1 and L2 are Regular
2. L1 is Regular but Not L2
3. L2 is Regular but Not L1
4. Both are not Regular

My Friend explained to me like this

Let us consider the language L2 first. Given that A is a regular set and the string denoted by 'y' $\in$ A, so we know that power which we take as concatenation of the string itself "n times ".

We are taking power of a language as concatenation "n" times with itself because:

Given a set V define

$V_0$ = {ε} (the language consisting only of the empty string),

$V_1$ = V

and define recursively the set

$V_{i+1}$ = { wv : w ∈ $V_i$ and v ∈ V } for each i > 0.

So $V_{i+1}$ is nothing but set comprising of concatenation of w and v where w belongs to $V_i$ which I am referring as $V_i$ and v belongs to V.

Reference : Definition and Notation Part of Kleene star

Now the set $V$ in this question is referred to the regular set A. We know that concatenation of regular language (or) regular set results in regular language only (by closure properties of regular language).

So X is generated by Y's concatenation only and $Y$ is a regular set (or) language. So $X$ is also going to be regular set.

Now coming to language L1.

Now it says the opposite i.e. $Y \in A $ only but now the relation between Y and X is: $Y = X^{n}$ and given the clause there exist associated with the value of $n$, so we can assign any value of n which is $>= 0$. So if $n = 1$, then $Y = X$ and hence $X$ is obviously regular set.

Similarly on setting $n = 2$, we get $Y = X^{2}$ meaning Y can be partitioned on exactly 2 halves and hence we can say X is half(Y). And we know given a language or a set L is regular, then half(L) is also regular.

Answer given as L1 is regular and NOT L2

What is the correct answer? How to solve this kind of questions?

Let A be a regular set. Consider the two sets below.

L1 = {$x \mid \exists{n}\geq 0 , \exists{y} \in A : y =x^{n}$}

L2 = {$x \mid \exists{n}\geq 0 , \exists{y} \in A : x =y^{n}$}

Which of the following is True?

1. L1 and L2 are Regular
2. L1 is Regular but Not L2
3. L2 is Regular but Not L1
4. Both are not Regular

What I know

$Y \in A $ only but now the relation between Y and X is: $Y = X^{n}$ and given the clause there exist associated with the value of $n$, so we can assign any value of n which is $>= 0$. So if $n = 1$, then $Y = X$ and hence $X$ is obviously regular set.

Similarly on setting $n = 2$, we get $Y = X^{2}$ meaning Y can be partitioned on exactly 2 halves and hence we can say X is half(Y). And we know given a language or a set L is regular, then half(L) is also regular.

With this understanding I came to a conclusion that L1 is Regular .

But, How to check the Regularity for L2 ? I also wanted to confirm my approach to L1 being Regular is correct .