CS 332: Theory of Computation Prof. Mark Bun Boston University February 1, 2021
Homework 1 – Due Thursday, February 4, 2021 at 11:59 PM
Reminder Collaboration is permitted, but you must write the solutions by yourself without as- sistance, and be ready to explain them orally to the course staff if asked. You must also identify your collaborators and write “Collaborators: none” if you worked by yourself. Getting solutions from outside sources such as the Web or students not enrolled in the class is strictly forbidden.
Problems There are 7 required problems and one bonus problem. Problems 1-5 and 7 are to be turned in via Gradescope. Problem 6 will be autograded using AutomataTutor.
1. For each of the following languages, (i) give a plain English description of the language, and (ii) give two examples of strings in the language and two examples of strings outside the language.
(a) L1 ={w∈{0,1}∗ |w=wR}
(b) L2 ={xaay|x,y∈{a,b}∗}∪{xbby|x,y∈{a,b}∗}
2. For each of the following languages, (i) describe the language using set-builder notation and union/intersection/complement/reverse/concatenation operations (the notation used in Problem 1), and (ii) give two examples of strings in the language and two examples of strings outside the lan- guage.
(a) L3 = the set of all strings over alphabet {a,b,c} that have length at least 3 and have b as their third symbol.
(b) L4 = the set of all strings over alphabet {0, 1} that either start with 0 and have odd length, or start with 1 and have even length.
3. Which of the following statements are true or false, for all alphabets Σ? For each, provide either a proof or a counterexample.
(a) For all strings x, y, z ∈ Σ∗, we have |x ◦ (yz)R| = |x| + |y| + |z|. (Recall that ◦ denotes concatenation.)
(b) ForalllanguagesL1,L2 ⊆Σ∗,wehave(L1◦L2)R =LR2 ◦LR1.
(c) ForalllanguagesL⊆Σ∗,wehaveL◦{ε}=L◦∅.
(d) ForalllanguagesL1,L2,L3 ⊆Σ∗,wehaveL1◦(L2∩L3)=(L1◦L2)∩(L1◦L3).
4. Consider the following state diagram of a DFA M using alphabet Σ = {A, B}.
B
q2 BB
AA startq0 A q1
1
(a) What is the start state of M?
(b) What is the set of accept states of M?
(c) Give a formal description of the machine M (i.e., as a 5-tuple).
(d) What sequence of states does the machine go through on input ABBAB?
(e) Does the machine accept the string ABBAA?
(f) Does the machine accept the string ABABAA?
(g) What is the language recognized by M? (Hint: It has a simple English description using modular arithmetic.)
5. No Problem 5 – this was about the formal definition of NFAs, which we did not get to in class, so it will be assigned on HW 2.
6. This problem will be autograded using AutomataTutor. Visit http://automatatutor.com/ and click on “Sign Up.” Make an account using your name and @bu.edu email address (it is important for recording grades that the information for your account match the information on the course list provided by the university). We’ll provide more specific information about how to register for this course on Piazza.
Give state diagrams of DFAs with as few states as you can recognizing the following languages. You may assume that the alphabet in each case is Σ = {0, 1}.
(a) L1 = {w | w begins with 1 and ends with 00}. (b) L2 = {w | w contains at most three 1’s}.
(c) L3 = {w | w contains the substring 010}.
Give state diagrams of NFAs with as few states as you can recognizing the following languages. You may assume that the alphabet in each case is Σ = {0, 1}.
(d) L4 = {w | w contains an even number of occurences of the substring 01}. (e) L5 = {w | w contains substrings 100 and 10 which do not overlap}.
7. Draw (and include in the PDF you submit to Gradescope) state diagrams of DFAs with as few states as you can recognizing the following languages. You may assume that the alphabet in each case is Σ = {0, 1}.
(a) L6 = {w | w is a string of the form x1y1x2y2 . . . xnyn for some natural number n such that xi,yi ∈ {0,1} and xi = yi for all i}.
(b) L7 = {w | w represents a binary number that is congruent to 1 modulo 3}. In other words, this number minus 1 is divisible by 3. The number is presented starting from the most significant bit and can have leading 0s.
Bonus Problem
(a) Give a state diagram of a DFA recognizing the language ADD = {w | w is a string of the form x1y1z1x2y2z2 . . . xnynzn for some natural number n such that x+y = z as binary numbers}. Here, x, y, z are presented starting from the least significant bit and can have trailing 0’s.
(b) Show that for any natural number n, the language M ODn = {w | w represents a binary number that is divisible by n} is regular. The number is presented starting from the most significant bit and can have leading 0’s.
2