CMSC 28000 — Problem Set 1

Instructions

This problem set is due on Wednesday January 15, 2020 at 18:00, to be submitted on Gradescope. Each problem is worth 10 marks in total.

Problems

  1. Let $\Sigma = \{0,1\}$. We define the complement of a word $w \in \Sigma^*$ to be the word $w$ with the 0s and 1s flipped, denoted $\overline w$. For example, if $w = 011101$, then $\overline w = 100010$.
    1. Give an inductive definition for the complement of a word.
    2. Show that $\overline{w^R} = \overline w^R$.
  2. Recall the definition of the extended transition function $\hat \delta : Q \times \Sigma^* \to Q$, given in Definition 2.10. Prove that for all $x,y \in \Sigma^*$ and $q \in Q$, $$\hat \delta(q,xy) = \hat \delta( \hat \delta(q,x),y).$$ Use induction to prove this and clearly state what you're performing induction on. For this problem, you should be careful to distinguish between $\delta$ and $\hat \delta$.
  3. For each of the following languages, give the formal definition of a DFA (that is, specify $Q,\Sigma,\delta,q_0,F$) that accepts the language and draw a state diagram. Briefly explain your construction. Formal proof is not necessary.
    1. The set of strings over $\{0,1\}$ that contain an even number of $1$s.
    2. The set of strings over $\{a,b\}$ that contain an odd number of $a$s and at most four $b$s.

Reflection

Once in a while, there will be a reflection section attached to a problem set. These are meant to give you an opportunity to reflect on your relationship with the course and the things you're learning. I will be reading and responding to your submissions, so this will also allow us to establish a dialogue about your learning in this course.

Completion of this part is optional but is worth an extra 10 marks in total. These will be loosely graded on completion/thoughtfulness and not "correctness" (i.e. what you think I want you to say); you should aim for about a paragraph or two of "thoughtfulness". Please start a new page with your responses when completing this section, separately from the problem set.

  1. What is your major? Which math and theoretical computer science courses have you previously taken?
  2. Why did you choose to take this course (CMSC/MATH 28000)? What are your expectations for this class? (Please feel free to be honest; I understand that there are many reasons for wanting to take a course, including more "practical" considerations)
  3. If you had to set a few concrete goals for this course, what would they be?
  4. Is there anything else you would like me to know at this point?