EECS 2001 Final: EECS2001 2012 Final Exam

• School: York University
• Department: Electrical Engineering and Computer Science
• Course: EECS 2001
• Professor: All

Document Summary

Course: cse2001 introduction to the theory of computation. No aids allowed: there should be 11 pages in the exam, including this page, write all answers on the examination paper. For each of the following languages, you must determine whether the language is regular, context- free, decidable, recognizable or not recognizable. For each language, circle the leftmost correct answer. For example, if a language is both recognizable and decidable, but not context-free, circle decidable. (a) {1p : p is a prime number} regular context-free decidable recognizable not recognizable. Let l2 = {w {a, b} : each letter in w appears at least twice in w}. For example, ababb and bb are in l2, but abbb is not in l2. Give a regular expression for the language accepted by the nite automaton shown below. Let l4 = {0i1j : i > j > 0}. Give an example of a non-regular language l such that l is regular.