Log In
0 votes

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?

  1. Both L1 and L2
  2. Only L2
  3. Only L1
  4. None

Ans. A. Both

Please explain.


in Theory of Computation
edited by
$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.

0 are right!


@Shobhit Joshi @Kunal Kadian

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

Can you please check this also




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

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 ??
0 far as I know.. :P

Please log in or register to answer this question.

Related questions

1 vote
1 answer
Let L = {w| w ∈ {0,1}*; w contains 01 and 011 as substring}. The number of states in the minimal DFA corresponding to the complement of L is equal to My Answer: Correct if I am wrong. Its complement will be all strings which don’t have 01 as substring. so if we make its dfa then minimum number of states will be 3. Answer given is 4
asked Jan 28, 2019 in Theory of Computation Mayank Bansal 272 views