CSC 320 Final: CSC 320 Final Exam Fall 2009

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

Document Summary

Sections a01 (crn 10867) and a02 (crn 10868) Students must count the number of pages in this examination paper before begin- ning to write, and report any discrepancy immediately to the invigilator. This exam 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. Csc 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. _____ i) {u u r v : u, v {0}+} _____ ii) {u u r v : u, v {0, 1}+}