Problem 1. Complete the TopHat worksheet titled Spring 2020 HW2.1. There are a total of 10 questions, each worth 2 points.
Problem 2. Prove that the regular expression r = (0∪1)∗ is not equivalent to PARITY.
Problem 3. For this problem, let Σ = {a,b}. Consider the problem of determining if a string has an odd length and does not end with bb.
3(a) State the problem as a decision problem.
3(b) Write the decision problem as a language.
3(c) Provide a regular expression that represents the language. Provide a brief justification as to why (i.e., what were your thoughts to construct it).
3(d) Build a DFA to recognize this language. Provide comments explaining how your process is working.
Hint: this language has the form of A∩B where A contains the odd length strings and B contains the strings ending with bb. You may want to consider using a modified version of the Cartesian product construction to recognize the union of two regular languages (see Theorem 1.25 and selected solutions for problem 1.4 for more insights, as well as our coverage in lecture).
Problem 4. Following the process of converting a DFA to a regular expression from lecture, convert the following DFA to an equivalent regular expression. Be sure to show all steps or you will receive no credit.
