GATE CSE 1988 | Question: 2ix

Question

What is the type of the language $L$, where $L=\{a^n b^n \mid 0 < n < 327 \text{-th prime number} \}$

Comments

Here n is finite and finite language must be regular Languages. 

# If n >0 and n not mentioned prime only then it would be DCFL.

# if n>0 and prime then it would be CSL

 

---

Why does this question contain algorithms tag?

Answer 1

Here $n$ is finite and finite language must be regular.

If $n$ is not restricted, then it would be DCFL.

Comments

but here limit is prime no.and we know that prime no. not belongs to regular lang.

pls clear my doubt if i'm wrong

---

Does nt matter with limit ... N is finite ... so regular ..

---

"If n is not restricted, then it would be DCFL"

Shouldn't be CSL?

---

sir, given language is $a^nb^n$, with no restriction on $n$, it would be DCFL

---

So no restriction means 327 is not given, right?
Still, it should be prime, No?

---

sir, i am taking no restriction as 'n' could be anything(no restriction on even being prime or non prime).

---

@Digvijay Pandey sir

$a^{n}b^{n} | n = prime\: number$

$a^{n}b^{n} | n = even\: number$

Are this languages CFL/NCFL ??

---

$L = {a^{1}b^{1}, a^{3}b^{3},a^{5}b^{5},a^{7}b^{7},...........}$

here though language is finie but how can we make FA so that all thses strings of L will be accepted??

please reply anyone.

---

Since it is finite but there is no particular pattern involved, the no of states required in a FA might be the summation of twice #a's and #b's across all the prime nos till the 327th prime no.

---

We will make a NFA which which will have various non-deterministic paths.

Like in one path it generates $ab$ in another path it generates $aabb$....in 326th path it generates $a^{326}b^{326}$

after making this convert the NFA to DFA

---

Basically creating separate DFA for all strings in that set & then eventually Union them.

---

Yes...it is also correct.

---

But sir here, 'n' is a power of both 'a' and 'b' and we know that Regular Language uses Finite Automata, but FA doesn't have memory to store n.

HOW CAN IT BE 'REGULAR LANGUAGE'?

---

@iwasifirshad But as you see $n$ is restricted to $0<n<327$^th  prime number, which makes the language finite. Hence Regular.

Answer 2

Regular language

Comments

Explain ....

---

Because it is finite and every finite language is regular....

---

Finite and u can think it as union of regular language .... Specific ...

---

Finite union