CS2333 Winter 2025 Assignment 2 PDF

CS2333 - Winter 2025 Assignment # 2 Due: Wednesday, January 22, by 11:00 pm Submission Instructions: Your answers should be submitted through the assignment dropbox on Desire2Learn. Please either submit as a single file or with...

CS2333 - Winter 2025 Assignment # 2 Due: Wednesday, January 22, by 11:00 pm Submission Instructions: Your answers should be submitted through the assignment dropbox on Desire2Learn. Please either submit as a single file or with one file per question. If you are submitting in a single file, name it CS2333-A2.hextni. Your answers should be in the same order as the questions. If you are submitting with one file per question, your files should be named CS2333-A2Q1.hextni , CS2333-A2Q2.hextni , and so on for each of the questions. In both cases, hextni should be the appropriate extension for your file type. D2L supports a variety of file types for submission and marker annotation, including.pdf,.docx,.png, and.jpg. Contact your instructor if you have any questions. All answers you submit must be your own work. You may discuss general approaches to assign- ment problems with your classmates. However, these must be general and cannot include things such as detailed steps of an algorithm or a proof. Please see the course syllabus for more details. Late assignment submissions will be considered only for medical reasons or in other exceptional circumstances, and normally only if the instructor is contacted before the assignment deadline. 1. (3 marks) Give languages L1 , L2 , and L3 such that L1 (L2 ∩ L3 ) = ∅ and L1 L2 ∩ L1 L3 is infinite and demonstrate these properties. 2. (12 marks) For each of the following finite automata, give: (i) the set of accept states; (ii) the sequence of states for the string ababba ; (iii) a description in words of the language of strings accepted by the automaton. (a) b b q1 a q2 q3 b a a CS2333 (Winter 2025) - Assignment 2 2 (b) q2 b b a, b q0 a q3 b a a q1 3. (25 marks) For each of the following languages over {0, 1}, draw the state diagram for a deter- ministic finite automaton that recognizes the language. (a) {w | the length of w is one more than a multiple of 3} (b) {w | w starts with 01} (c) {w | w starts and ends with the same symbol} (d) {w | w has an odd number of 1s and an even number of 0s } (e) {w | w has length at least 3 and its third symbol is 0 }