5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – Raphael Oct 27 '16 at 9:42
  • $\begingroup$ See our reference question for either direction. $\endgroup$ – Raphael Oct 27 '16 at 9:44
  • 2
    $\begingroup$ @Raphael It is not an yes/no question . I dont know what made you think like that . Question along with my approach is given but it is wrong. I am waiting for a subject expert to properly explain why L2 is not regular $\endgroup$ – pC_ Oct 27 '16 at 10:18
7
$\begingroup$

Your reasoning regarding $L_1$ is wrong. What you show is that for each $n$, the following language is regular whenever $A$ is regular: $$ L_1^{(n)} = \{ x : x^n \in A \}. $$ The language $L_1$ is the infinite union of $L_1^{(n)}$ for all $n \geq 0$. Unfortunately, regular languages are not closed under infinite union (for example, every unary language is an infinite union of singleton languages).

Nevertheless, $L_1$ is regular. Given a DFA $\langle Q,q_0,F,\delta \rangle$ for $A$, we construct a DFA for $L_1$ whose set of states is the set of all functions $Q \to Q$. The initial state $id$ is the identity function, and we construction the automaton so that $\delta_{L_1}(id,w)$ is the function that maps $\sigma \in Q$ to $\delta(\sigma,w)$. This gives us enough information to determine whether any power of $w$ belongs to $A$.

The language $L_2$, in contrast, is not necessarily regular. For example, if $A = ab^*$ then $L_2 \cap ab^*ab^* = \{ ab^n ab^n : n \geq 0 \}$, which isn't regular.

$\endgroup$
  • 1
    $\begingroup$ @Yuval_Filmus sir , if $A=ab^{*}$ Then what will be the $L_{2}$ ? Im not getting this part . Why did you take intersection with $ab^{∗}ab^{∗}$ Could you please add little more explanations to your solution . Im not that good in this subject . Thanks :) $\endgroup$ – pC_ Oct 27 '16 at 13:19
  • 3
    $\begingroup$ You'll have to work it out on your own. This is the only way to become better. $\endgroup$ – Yuval Filmus Oct 27 '16 at 13:27
4
$\begingroup$

A possible way to prove that $L_1$ is regular is to use finite monoids. A language $A$ of $\Sigma^*$ is recognised by a finite monoid $M$ if there is a surjective monoid morphism $f:\Sigma^* \to M$ and a subset $P$ of $M$ such that $f^{-1}(P) = A$.

Now let $Q = \{ x \in M \mid \text{there exists $n\geqslant 0$ such that $x^n \in P$}\}$. Then \begin{align} f^{-1}(Q) &= \{ u \in \Sigma^* \mid f(u) \in Q \} = \{ u \in \Sigma^* \mid \text{there exists $n\geqslant 0$ such that $f(u)^n \in P$} \}\\ &= \{ u \in \Sigma^* \mid \text{there exists $n \geqslant 0$ such that $f(u^n) \in P$} \} \\ &= \{ u \in \Sigma^* \mid \text{there exists $n \geqslant 0$ such that $u^n \in A$}\} = L_1 \end{align} Thus $L_1$ is regular. This method actually shows that if $M$ recognizes $A$, then it also recognizes $L_1$. This is useful to prove further properties: for instance if $A$ is star-free, so is $L_1$.

EDIT. See Yuval Filmus' answer for a proof that $L_2$ is not regular. My first answer for this part was plain wrong and has been deleted.

$\endgroup$
  • $\begingroup$ Sir, How did you find complement of $L_{2}$ ? I couldn't understand how did you get it as $P =\{ a^{p} | p$ $is$$ prime \} $ $\endgroup$ – pC_ Oct 31 '16 at 13:38
  • $\begingroup$ Well, if $n = 0$, $(a^{pq})^n = a^0$. If $n = 1$, $(a^{pq})^n = a^{pq}$ and if $n \geqslant 2$, then $(a^{pq})^n = a^{pqn}$. Thus $L_2 = \{a^0\} \cup \{a^r \mid r \text{ is a product of at least 2 numbers } \geqslant 2\}$. Now, what is the definition of a prime number? $\endgroup$ – J.-E. Pin Oct 31 '16 at 13:51

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.