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.