CSC 320 Final: CSC 320 Final Exam Summer 2008

• School: University of Victoria
• Department: Computer Science
• Course: CSC 320
• Professor: All

Document Summary

Students must count the number of pages in this examination paper before beginning to write, and report any discrepancy immediately to the invigila- tor. This question paper has ten pages (the last page is blank in case you need extra space) plus the header page. Use only space provided on exam for answering questions. [20 marks] for each of the following languages, indicate the most restrictive of the classes below into which it falls. Cs 320- page 1 of 10 (a) nite (b) regular (c) context-free (d) turing-decidable (e) turing-acceptable (f) none of the above. L = { an bn : n 0} the correct answer is (c) since l is context-free, but is not regular. _____ ii) { w {1 }* : w is the unary notation for the integer 10k, k 0} _____ iii) { w { 0,1 }* : w is the decimal notation for the integer 10 i , i 0 }