Test Paper

Question

If language a^m b^n | m,n>=1 and gcd(m,n)=1}, then L is

(A) Context Free Language (B) Context Sensitive Language

(C Regular Language (D) None of the above

Comments

Is it b?

---

gcd(m,n)=1 means m,n should be prime no and also given that m,n>=1

so it should be CSL

---

It is not necessary that they should be prime, instead of that the condition is the two numbers should not share there prime factorization. Eg 8 and 9 they do not share there prime factorization and have gcd 1.

Answer 1

Context Sensitive Language because you have to remember the a and b in division operations. So a LBA can do this because it can do memory operations.