CMPSC464 Name:
Midterm Exam 1
09/30/2021
Time Limit: 75 Minutes
Copyright By PowCoder代写 加微信 powcoder
This exam contains 9 pages (including this cover page, double-sided) and 6 questions.
Total of points is 100.
This will contribute to 25 % of your total grade
Grade Table (for grader use only)
Question Points Score
Total: 100
CMPSC464 Midterm Exam 1 – Page 2 of 9 09/30/2021
1. (10 points) True or False Questions (Leaving an empty box will result in 0 pt)
(a) (1 point) A regular language is accepted by some Turing Machine.
(b) (1 point) A decidable language is accepted by some NFA.
(c) (1 point) If there exists a Nondeterministic Turing Machine (NTM) which accepts
some language A, then there exists a Deterministic Turing Machine which accepts
(d) (1 point) The set of even numbers (viewed as a binary string) is decidable.
(e) (1 point) If A is recognizable and A is recognizable then A is decidable.
(f) (1 point) There exists some language A where A is decidable but A is not decidable.
(g) (1 point) If A is regular, then A is regular.
(h) (1 point) If A is decidable and B is decidable, then A ◦B (concatenation) is decid-
(i) (1 point) If B is regular and A ≤m B, then A is regular.
(j) (1 point) If A is decidable by a Turing Machine, then it is decidable by a wordRAM.
CMPSC464 Midterm Exam 1 – Page 3 of 9 09/30/2021
2. (10 points) Fill in the blank. For runtime questions, points will be only given to the
simplest asymptotic form. (Leaving an empty box will result in 0 pt)
(a) (3 points) Suppose F = {s1}. Give an example of string in {A,B}∗ that is accepted
by this DFA.
(b) (3 points) Suppose F = {s0, s1, s2}. Give an example of string in {A,B}∗ that is
rejected by this DFA.
(c) (4 points) Suppose F = {s1, s2}. Give a full description of strings in {A,B}∗ that
is accepted by this DFA.
CMPSC464 Midterm Exam 1 – Page 4 of 9 09/30/2021
3. (20 points) Consider A = {w ∈ {0, 1}∗|w has equal number of zeroes and ones}. Leav-
ing Blank will result in 2 pts per part.
(a) (10 points) Use the pumping lemma to show that A is not regular.
CMPSC464 Midterm Exam 1 – Page 5 of 9 09/30/2021
(b) (10 points) Suppose we have a Turing machine for A. Suppose we have B = {w ∈
{0, 1}∗| w has exactly one more zeroes than ones}. Show that B ≤m A. (Hint:
exhibit the computable function f)
CMPSC464 Midterm Exam 1 – Page 6 of 9 09/30/2021
4. (30 points) Let a ∈ {0, 1}∗. Define binary(a) as
binary(a) =
Note that this is equivalent to having a as a binary representation of some real number
between 0 and 1. Leaving Blank will result in 3 pts per part.
(a) (15 points) With some fixed a (thereby a having some finite length), consider
Aa := {x ∈ {0, 1}∗| binary(x) < a}. Show that Aa is regular. CMPSC464 Midterm Exam 1 - Page 7 of 9 09/30/2021 (b) (15 points) Let A be defined as A := {x#y|x, y ∈ {0, 1}∗ binary(x) + binary(y) < 1} Is A regular? Why or why not? CMPSC464 Midterm Exam 1 - Page 8 of 9 09/30/2021 5. (10 points) Let x, y ∈ {0, 1}. Design a Boolean circuit that computes f(x, y) := 0 if x 6= y 1 if x = y using AND, NOT , OR gates of fan-in at most 2. Leaving Blank will result in 2 pts. CMPSC464 Midterm Exam 1 - Page 9 of 9 09/30/2021 6. (20 points) Suppose we define EQDFA as the following. EQDFA := {(M1,M2) : M1,M2 are DFA , L(M1) = L(M2)} Show that EQDFA is decidable. Leaving Blank will result in 4 pts. 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com