MadeEasy Full Length Test 2019: Theory of Computation - Identify Class Languages

Question

Consider the following language over ∑={0,1}

$L_{1} = \left \{ a^{\left \lfloor \frac{m}{n} \right \rfloor}| m,n \geq 1; n<m \right \}$

$L_{2} = \left \{ a^{m^{n}}| m,n \geq 1; n<m \right \}$

Which of them are regular?

• A. Both L1 and L2
• B. Only L2
• C. Only L1
• D. None

Ans. A. Both

Please explain.

 

Comments

$L_1=\left \{ a^{ \left\lfloor \frac{m}{1} \right\rfloor} :n=1,m>=2 \right \}\bigcup \left \{ a^{ \left\lfloor \frac{m}{n} \right\rfloor} :n<m,n,m>=1 \right \}$

$\left \{ a^{ \left\lfloor \frac{m}{1} \right\rfloor} :n=1,m>=2 \right \}=\left \{ a^x:x>=2 \right \}$

So, $L_1=\left \{ a^x:x>=2 \right \}$

So, $L_1$ is regular

$L_2=\left \{ a^{ m^1} :n=1,m>=2 \right \}\bigcup \left \{ a^{ m^n} :n<m,n,m>=1 \right \}$

$\left \{ a^{ m^1} :n=1,m>=2 \right \}=\left \{a^x:x>=2\right \}$

So, $L_1=\left \{ a^x:x>=2 \right \}$

So, $L_2$ is regular

---

@Shobhit Joshi

I didn't get it clearly,

how did you make the conclusion in 2nd line of both the cases. You took union right? But the inference drawn in the 2nd line seems that you did intersection..

Can you explain a bit more?

---

Both are regular.

For L1, make n=1. That would satisfy the condition n<m and n>=1. So the language becomes L1={a^m | m>=1} which is regular.

Similarly for L2, make n=1.That would satisfy the condition n<m and n>=1. So L2 becomes L2={a^m | m>=1} which is same as L1 and hence regular.

---

@Somoshree Datta 5

but what if n is something other than 1?

For L1:

m=3 then n can be 1,2 --> L = {aaa,a}

m=4, n can be 1,2,3 --> L = {aaaa,aa,a}

m=5,  n can be 1,2,3,4 --> L={aaaaa,aa,a}

So how do we form a regular expression?

---

I thought like this,

L1 is actually this = {aa,aaa,aaaa,...} bcoz any number greater than 1 can be expressed in the form floor(m/n) by keeping n as 1.

L2 is also = {aa,aaa,aaaa,...} bcoz any number greater than 1 can be expressed in the form $m^n$ where n= 1

So here actually, L1= L2 = aaa* . Hence both are Regular.

Is this way Correct ?

---

Take any value of m and n and check it will always belong to the language L. So regular expression for L1 is aa*.

for L={aaa,a}, here if u take m=3, n=1 and m=1,n=1 still the strings belong to L1. There is always an alternative way to write m for any value of m and n u give.

---

@MiNiPanda I did union, all the other will be the subset of $a^x:x\geq2$. So, doesn't matter what the other are.

---

@Shobhit Joshi,@Kunal Kadian,@Somoshree Datta 5

Thanks guys.. I have understood now :)

One thing, secondary indexing is always dense or may be sparse sometimes?

---

@Somoshree Datta 5 I think aa will not belong to L1 and L2 here bcoz n<m . Here L1= L2= aaa*

---

@MiNiPanda always dense, as it is on non-ordered attribute

---

@MiNiPanda Secondary indexing is always dense, Never sparse.

---

Kunal Kadian yes..you are right!

---

@Shobhit Joshi @Kunal Kadian

Thank you..This paper has lots of mistakes :(

Can you please check this also https://gateoverflow.in/295101/made-easy-gate-mock-1-question-56

 

---

https://gateoverflow.in/3003/consider-the-following-statement-about-indexes

@MiNiPanda

@Shobhit Joshi

@Kunal Kadian

@Somoshree Datta 5

read this

---

@Magma 

i checked the link.. there I found another link of nptel lecture 

https://nptel.ac.in/courses/106106093/12

There the professor clearly mentioned that secondary index is always dense.

You can visit the link. I am attaching the screenshot here.

---

In my notes  I have also written that "secondary index is always dense "

what the link that I provide in that comment section after see the image which was posted by minal from reference : given in navathe   then have doubt in it

 

but yeah If  IIT  professor clearly mentioned that secondary index is always dense.  then there's not no point to discuss on this

---

Yeah saw that.. :/

This one is from Korth

---

Hmm this  Made-easy Mock1 has lots of mistakes  ~_~

btw both B+ / B  tree use both sparse as well dense nah ??

---

Yes..as far as I know.. :P