Virtual Gate Test Series: Theory Of Computation - Regular Languages

Question

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

Comments

But in Peter lenz i read that if any language L is regular, then L²,L³.... so on, are also regular.Following this L2 is also regular.  Correct me if im wrong. And can anybody briefly explain reg.languages vs rer.set? thanks.

Answer 1

Let us consider the language 2 first.Given that A is a regular set and the string denoted by 'y' belongs to the set 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₀ = {ε} (the language consisting only of the empty string),

V₁ = 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ⁱ  and v belongs to V. 

Reference : Definition and Notation Part of https://en.wikipedia.org/wiki/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 1.

Now it says the opposite i.e. Y belongs to A only but now the relation between Y and X is :  Y  =  Xⁿ  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²  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.

Hence the 1st language is also regular .

Hence A) should be the correct option.

Comments

I'll try :)

---

@arjun sir , Not really. I have just started learing TOC . It will take atleast a week for me to undrsatand many things in this discussions .

I have asked @kapil sir how did he proved L2 Non Regular but didn't get any reply . May be he is busy.

Using counter exaples L2 is being proved Not Regular . But I dont know how to think like this in exam

What I think for now  is ,

L1 is regular because L1 is A*.. regular languages are closed under kleen operation..

L2 is not regular because L2 contains strings like A^(1/2), A^(1/3), A^(1/4)... we cannot acheive this using any finite automata..

May be @Praveen_Saini sir could help ? I think he is master in TOC :)

---

@pC , I am sorry. Actually i was thinking to prove L1 regular by a DFA but didn't get it.  okk, and surely i will post why L2 is non regular, once Arjun sir simplify DFA for L1 :)

Answer 2

Here y is a regular set

As y∊ A and A is a regular set

Here y=xⁿ

So, here xⁿ have to be regular

But in x= yⁿ

 y is regular but yⁿ  may  not be regular

say y = $\sum0^n$

$U=0^p,V=0^q,W=0^r$

Now p+q+r$\leq$n

Now when i=0

then equation not satisfied

So, here x=yⁿ is not regular

Comments

yⁿ is nth term of y

then aⁿbⁿ is nth term of a*b*

---

@Sreshtha. y$\epsilon$A that doesnt mean y is regular.

for e.g A = $\sum$^* and y=aⁿbⁿ  then ?

---

@sreshtha. Sorry for the wrong previous comment.

Answer 3

Answer : B

https://cs.stackexchange.com/questions/65176/check-the-regularity-of-the-folowing-languages

I don't know the reasoning for $L_1$ right now. But I can easily say that $L_2$ is Not Regular.

Consider $A = ab^*$

Now, $L_2 = (a)^* + (ab)^* + (abb)^* + (abbb)^* + ....$ Which is Non-regular.