Exam 2 EECS 4100 (No aids allowed Name 1. (36%). Circle Tri\" Fula\" arul jisury

Question

Exam 2 EECS 4100 (No aids allowed Name 1. (36%). Circle Tri" Fula" arul jisury your answer ni.. mark, will be given i..dm (a) It is decidablo that a given context free grammar generales an nfinite poukes f sis a justification is provided (b) If t is a regular tanguage, and.then t is a regpslar lengngs True (e) An NFA with & states can be modeled by a DEA with states? True (d) we can prove that language A is decolable by constructing a Turing machine Maut decides A. True False (e) Every recursive language is recursively enumerable False True la. b) (t) Do the following pair of regular expressions define the same language over the alphabet? (2) a(ab) True False (g) Consider the following algorithm: n- 4 while ( n is the sum of two prime numbers) n=n+2 We can construct a Turing machine such that it determines if the above algorthm ever True False

Explanation / Answer

1. (a) True. It is decidable that a CFG generates infinite number of strings.

(b) False

(c)True

(d)True

(e)True

(f)True

(g)False

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

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