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.
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.
0
1
1 01
01
1
0
0
1
1
0
0
Σ
(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.
E represents even and O represents odd. Each state’s name contains two letters, the first corresponds to the length of the string read so far, and the second corresponds to the number of 1’s in the string read so far.
Problem 2.
EE
1
1
OO
0000 1
OE
EO
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.
2
1
All unspecified transitions go to the reject state.
1 : 1, R
⊢:⊢, R 0 : 0, R 0 : 0, R 0 : 0, R
1 : 1, R 1 : 1, R
1 : 1, R 0 : 0, R
: , R
T
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.
Proof For all n ∈ N, the first extension of string z = 10n1 is 0n, thus A(1) = {0n |∀n ∈ N} . z∈{10n1}
Since A(1) ⊇ A(1) and |A(1) | = ∞, then |A(1)| = ∞, and by ordinal extension nonregu- z∈{10n1} z∈{10n1}
larity theorem, A is not regular.
Problem 5. (50 points) Prove: For every k ∈ N, the language Ak ={0n1n|n≤k}
is regular.
Proof For any k, {0n1n|n ≤ k} is finite, and any finite language 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.
Proof (There are lots of proofs, but I think this is the easiest.)
Let A = {0n1n} and B = AC. Both are nonregular (A from class, B because the complement of any nonregular language is nonregular by closure properties). A ∩ B = ∅ and A ∪ B = Σ∗, both of which are regular.
3