CS 332: Elements of Theory of Computation Prof. Mark Bun
Boston University
February 18, 2021
Test 1
Read all the instructions on this page before beginning the exam.
Your solutions must be scanned and uploaded to Gradescope by 11:59PM Eastern Standard
Time, Thursday February 25, 2020.
We are flexible with the format in which you complete the exam and upload the solutions. Blank space is provided if you wish to print the exam out and write your solutions on it, or if you wish to download the PDF and fill it out on a tablet. You may also prepare your solutions on your own paper as if you were completing a homework assignment. Both handwritten and typeset solutions are allowed. Make sure to clearly indicate which problem you are solving, both on your written solution and when you submit to Gradescope.
This exam contains 4 problems, some with multiple parts. The test is worth 100 points. At the end of the exam, there is a (harder and completely optional) bonus problem 7. If you attempt this problem, it will be accounted for in the same way bonus homework problems are.
The exam is open-book in that you may freely consult the Sipser textbook, lecture notes and videos posted online, past homework assignments and solutions, discussion worksheets, your own class notes, and discussions on Piazza. You may not use any outside resources beyond those listed here.
You must complete the exam by yourself. No collaboration with anyone is permitted.
You do not need to spend time and paper rederiving facts that we have studied. You may cite known results and examples which were stated in lecture or proved in the main body of the text. This does not include homework problems, discussion section problems, or the solved exercises/problems in the text. You are, of course, free to use such results but you have to prove them first.
You will be graded not only on the correctness of your answer, but also on the clarity with which you express it. Make your writing large and neat.
If you need to ask a clarification question about one of the problems, please do so in an instructor- only post on Piazza. If the course staff believes your question may be a common one, we will change the settings of your post to be public to the class, keeping your identity anonymous.
Good luck! We hope you have fun solving these problems.
1
Problem 1 (True or False, 20 points). Indicate whether each of the following statements is true or false. Justify your answer in two or three sentences. False statements should be justified by a specific counterexample. No points will be given even for a correct answer if no justification is presented.
(a) If A is a finite language and B is a regular language, then A ∩ B is regular.
(b) If A ∪ B is a regular language, then A and B are both regular.
(c) Every NFA with k states can be converted to an equivalent DFA with 4k (or fewer) states.
(d) For all regular expressions R and S, we have L((R ∪ S)∗) = L(R∗ ∪ S∗).
(e) If a language L has a pairwise distinguishable set of size 16, then every DFA recognizing L requires size at least 4.
Problem 2 (Regular Languages).
Consider the language A = {w ∈ {0, 1}∗ | (w contains the substring 001) OR (w contains at most two 0’s)}.
(a) Draw the state diagram of a nondeterministic finite automaton recognizing A, using the fewest number of states you can. (10 points)
(b) If you were to use the generic construction we saw in class for converting this NFA into a DFA, how many states would the resulting DFA have? You do not need to simplify this DFA or show what it looks like. Your answer should be an integer between 1 and 999. Briefly justify your answer. (5 points)
(c) Give a regular expression generating A. (5 points)
(d) Let M = (Q,Σ,δ,q0,F) be an DFA recognizing a language L. Give the formal description of
an NFA recognizing L. (5 points)
Problem3(ClosureofRegularLanguages). ForlanguagesA,BdefinetheoperationFUSE(A,B)=
{xy|x∈A,yR ∈B}.
(a) If A = L((01)∗) and B = L(1∗0∗), give a regular expression describing FUSE(A,B). (5
points)
(b) Describe an algorithm taking as input a regular expression S and outputting a regular ex-
pression generating (L(S))R. Briefly justify why your algorithm works. Hint: use the inductive structure of a regular expression. (10 points)
(c) Let M1,M2 be DFAs. Explain how you could generically construct a DFA for the language FUSE(L(M1),L(M2)). State the type (DFA, regex, etc.) of each intermediate object con- structed in the process and explain in a sentence what conversion procedure is used to obtain each object from the previous one.
Hint: You can cite the algorithm from part (b) for one of these steps. You can get full credit for this question even if your solution to (b) wasn’t correct. (10 points)
2
Problem 4 (Non-Regular Languages).
(a) Let L = {x#y | x,y ∈ {0,1}∗,|x| = |y|, and x ̸= y}. Show that L is not regular. (10 points)
(b) For any integer k ≥ 0, define Lk = {0nk | n ≥ 0}. For which values of k is Lk regular? Prove your answer.
Hint: You may use, without proof, the fact that for every k ≥ 2 and 0 ≤ m < n, we have nk + (m + 1)k − mk < (n + 1)k. (10 points)
(c) Your classmate thinks applying the distinguishing set method is too annoying, and has sug- gested a shortcut. They suggest the following weaker definition of a pairwise distinguish- able set, which they’re calling a “somewhat distinguishable set” for a language. A set S is somewhat-distinguishable for a language L if there exists x ∈ S such that for all y ∈ S with y ̸= x, there is a distinguishing extension z for x,y. How is the definition of a somewhat- distinguishable set different from that of a pairwise distinguishable set? (5 points)
(d) Your classmate claims that if a language L has an infinite somewhat-distinguishable set S, then L is non-regular. Prove your classmate correct or describe a counterexample. (5 points)
Problem 5 (Bonus Problem). For a language L, define D(L) = {ww | w ∈ L}.
(a) Give an example of a regular language L such that D(L) is not regular.
(b) Show that for every language L, if D(L) is regular, then L is regular as well.
(c) A two-pass DFA is like a DFA, except it gets to read its input twice (left-to-right both times) before making an accept or reject decision. Use part (b) to show that two-pass DFAs are no more powerful than ordinary DFAs: every language recognizable by a two-pass DFA is also recognizable by an ordinary DFA.
3