EECS 2001 Midterm: EECS2001 Test 1 2012

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

Document Summary

You may use any result that was proved in class or in the textbook without reproving it. Make sure your test has 5 pages, including this cover page. Answer in the space provided. (if you need more space, use the reverse side of the page and indicate clearly which part of your work should be marked. ) Let l = {w {a, b} : w does not contain the substring aab}. For example, babb and ba are in l, but bbaaba is not in l. draw a deterministic nite automaton for l. Write a regular expression that describes the language accepted by the automaton shown below. We de ne a function f : as follows. For any x , f (x) is the string obtained by replacing each occurrence of b in x by cc. For example, f (ab) = acc, f (cab) = cacc and f (bc) = ccc.