CSC 320 Midterm: CSC 320 UVic Midtermk10

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

Document Summary

Put your name on every page of the exam. You should have 7 pages including this header page. 1. (a) [10 marks] prove that the language. L = {w {0, 1}* : w has 0 1 as a pre x and 1 0 as a suf x } is regular by designing a dfa which accepts l. L = {w {a, b}* : w contains both a b a and b a a b as substrings } is regular by giving a regular expression which generates l. (c) [10 marks] design a context-free grammar which generates the language. L = {cr w cs w r ct. : w {a, b}*, r, t 1 and s 0}. [25 marks] use the construction described in class (which is the same as the one in the text) to convert this ndfa to an equivalent dfa: 3. (a) [5 marks] state the pumping lemma for regular languages.