Problem 2. Guess the classification for each of the following languages as eithe

Question

Problem 2. Guess the classification for each of the following languages as either r r.e. but not not co-r.e corr.e. but not r e or neither r.e. or co-r.e. No justification. is required. 2.1 M, k) M is a TM that accepts at least one string of length 2.2 f (M, k) Mis a TM that accepts at most one string of length k 2.3 {KM) M is a TM and M has 50 states) 2.4 f M) M is a TM and L(M) contains a palindrome 2.5 {KM) M is a TM and L(M) 2.6 (M) M is a TM and L(M) is r e 2.7 {KM) M is a TM and LCM) is decidable 2.8 10G) G is a CFG and L (G) 2.9 (M) M is a C-program that halts on (M) 2.10 t (M): M is a TM that sometimes diverges 2.11 (M, w) M is a TM and M that uses at most 50 tape cells when run on w 2.12 f (G) G is a CFG and G accepts an odd-length string). 2.13 (M) M is a smallest (fewest-state NFA for L(M) 2.14 p is a multivariate polynomial and p(x) 0 for some x E Z" 2.15 (p, q) p and g are multivariate polynomials and p x) x) for all x E Z

Explanation / Answer

Ans-2.1 r.e.

Ans 2.2 r.e.

Ans2.3 - recurcive

Ans 2.4 - co-r.e.

Ans2.5 - co-r.e.

Ans 2.6 - recursive

Ans 2.7 - neither

Ans 2.8 - but not r.e.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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