Qualifier Practice Exam : Foundations

Part III: Theory of Computation (40 pts)
Question 1 (3 Points): Consider the following language over the alphabet of the 10
decimal digits (i.e., {0, 1, , 2, 3, 4, 5, 6, 7, 8, 9}):
L = {n : n = closing price of oil rounded to nearest U.S. dollar on Dec. 29, 2017}
What is the smallest class of languages of which L is a member?

(a) Languages decidable in linear deterministic time.
(b) NP
(c) NP-complete languages (?)
(d) P
(e) The undecidable languages

Question 2 (3 Points): The FUBAR problem is a new decision problem that you have
just begun to study. So far you have been able to show the following two things about the
FUBAR problem:
• There is a polynomial-time reduction from the Satisfiability problem (“Is a given
Boolean formula satisfiable?”) to the FUBAR problem.
• You have a nondeterministic method that solves the FUBAR problem and that never
consumes more than a polynomial amount of space.
What do you know for sure about the FUBAR problem given current knowledge?
(a) It is NP complete
(b) It is in the complexity class NP
(c) It is in the complexity class P
(d) It is not in the complexity class P
(e) It is NP hard.

Question 3 (4 Points): The minimum number of states of a Deterministic Finite State
Automaton (DFSA) over the alphabet {0, 1} recognizing the language containing the single
string of n 0s (n is fixed) is:
(a) 2n (b) n + 2 (c) n^2 (d) 10. (no)
Not sure if this is saying 0*1*(0^n)1*0* or just 0^n

Question 4 (4 Points): Let L be the language over {0, 1} consisting of all strings that
have a 1 in the third symbol from the end (e.g., the string 0100 is in L). The minimum
number of states of a DFSA recognizing L is:
(a) 50 (b) 5 (c) 8 (d) 100.