COMS 331: Theory of Computing, Fall 2021
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
COMS 331: Theory of Computing, Fall 2021
Midterm Exam
Problem 1. (50 points) Let A be the set of all strings x G {0」}* such that the string 001 (with these three bits consecutive) occurs in exactly two places in x. (Examples: 001 001 G A and 1001010010 G A, but 001 G A and 100100100
Design a DFA M such that L(M) = A.
Problem 2. (50 points) Prove: For every k G N, the language
Ak = {x G {0,1}* | #(1, x) < k}
is regular, where #(1,x) is the number of 1's in x.
Problem 3. (50 points) Let
A = {x G {0,1}* | #(1,x) is even if and only if |x| is a multiple of 3}.
(Recall that P if and only if Q means that P and Q are both true or both false.) Design a DFA M such that L(M) = A.
Problem 4. (50 points) Prove: For every n G N, there is a regular language A C {0,1}* such that A is not decided by any n-state DFA.
Problem 5. (100 points) In each of the following, either give an example of languages A and B with the indicated property or state that no such languages A and B exist.
(a) A is regular and B is not regular.
(b) A is regular, B C A, and B is not regular.
(c) A is regular, B is regular, and A A B is not regular.
(d) A is regular, B is not regular, and A A B is regular.
2021-12-06