The Gateway to Computer Science Excellence
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 by Boss (23.5k points)
edited by | 220 views
$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.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,309 answers
105,025 users