COMS 331: Theory of Computing, Spring 2021 Midterm Exam
10:00AM-10:00PM, Wednesday, March 24, on Gradesccope.
You have TWO hours to complete and submit this exam. There are six problems, worth 50 points each. Any problem that you leave blank or indicate clearly that you do not want graded will receive 30% credit (15 points). Every other problem will be graded and receive 0-50 points. All answers should be explained, at least briefly.
While taking the exam you MAY
• consult your own notes and the lecture notes;
• consult the textbook and the class lectures;
• contact the instructor or TA with questions about the exam. (We’ll try to answer promptly, but cannot guarantee that.)
While taking the exam you may NOT
• post questions or any information about the exam;
• discuss the exam with anyone except the instructor and TAs;
• work with anyone else or access any other resources or websites.
If you would like tex file of this exam, please go to https://iastate.box.com/s/d0piboex6bz6ge3a2m089hh07omasstd.
1
Problem 1. (50 points) Let A be the set of all strings x ∈ {0, 1}∗ such that, every time the bits 1101 occur consecutively in x, they are immediately followed by the bits 001. (Note: If 1101 does notappearinx,thenx∈A.) DesignaDFAM suchthatL(M)=A.
Problem 2. (50 points) Let A = {x ∈ {0, 1}∗ | exactly one of |x| and #(1, x) is odd}, where #(1,x) is the number of 1’s in x. Design a DFA M such that L(M) = A.
Problem 3. (50 points) Let A = {10m10n1 | m, n ∈ N and m+n is odd}. Design a Turing machine M such that L(M) = A.
Problem 4. (50 points) Prove that the language A={x10n1y|x,y∈{0,1}∗ andn=|x|+|y|}
is not regular.
NOTE: A proof using the pumping lemma will receive full credit if correct, but is not eligible for partial credit. The ordinal extension nonregularity method is recommended here.
Problem 5. (50 points) Prove: For every k ∈ N, the language Ak ={0n1n|n≤k}
is regular.
Problem 6. (50 points) Prove or disprove: For all languages A, B ⊆ {0, 1}∗, if A ∩ B and A ∪ B are regular, then A and B are regular.
2