CSC 320 Midterm: CSC 320 UVic Midterm97

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

Document Summary

[30 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: a u e v s a b t e b. 2. (a) [10 marks] state the pumping lemma for regular languages (as presented in class, (b) (c) (d) [10 marks] let w = an bm cn+m. Describe precisely by giving several cases all pos- sible ways of choosing x, y, z such that w = xyz, and y . [10 marks] apply the pumping lemma to w = an bm cn+m to prove that. L = {an bm c p : p n + m} is not accepted by a dfa with 2 * n + 2 * m states. [10 marks] a more judicious choice for w would have made the argument for (c) much simpler.