Given below are some categories of languages. (R) Regular Languages (C) Context

Question

Given below are some categories of languages. (R) Regular Languages (C) Context Free Languages (P) Polynomail Time Languages (NP) Nondeterministically Polynomial Time Languages. (D) Decidable Languages (T) Recognizable Languages (L) All Languages Classify each of the languages below into the smallest category (from above) that they provably belong. Each correct answer is 1 point. L = {w | w sum {0, 1}*, value (w) = 5} where value (w) represents the value of the binary string in decimal. S_TM = {lt M gt | 011 sum L(M)} L = {0^2n | n > 0} L = {w | w sum {0, 1}* such that value (w) is prime} E_TM bar where E_TM = {lt M gt | L (M) = 0} PrimeFactor = {lt m, n gt | n is a prime factor for m} L = {0, 1}*{0^n 1^n|n > 0} where represents the set difference operation. L = {0^n 1^m 2^I 3^n | n > 0, m > 0, l > 0, m lessthanorequalto l} KnightPath = {lt n, s, t gt | there exists a sequence of knight moves on an n times n chess board form the square s to the square t} A language B such that A_TM bar lessthanorequalto m B.

Explanation / Answer

1) R(Since we can construct a FA for it)

2) R(Since we can construct a FA for it)

3) C(The Number of 0's are power of 2 which needs Grammar)

4) T( We need a Turing machine for it)

5) L(We have to Consider an Empty Set for it)

6) T( We need a Turing machine for it)

7) C(We can Construct CFG and mark final as Non Final States)

8) T( We can Simply recognize using TM)

9) NP( Since the size was Not Mentioned we cannot determine)

10) P( We can solve in Polynomial Time)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.