Description
Problem 1 (15 points)
Use Proof By Contradiction to show that for any k ≥ 2, √k
2 is an
irrational number.
2 / 7
CS 331: Theory of Computing
Problem 2 (15 points)
The depth (or height) of a tree is the number of edges along the
path from the root node to the deepest leaf node. A full binary
tree is a tree in which every node other than the leaves has two
children. A full binary tree is called perfect if all leaves are at the
same depth. Note that the single root is a perfect binary tree with
depth 0.
Use Proof By Induction to show that for every n ≥ 0, a depth n
perfect binary tree has 2n+1 − 1 nodes.
3 / 7
CS 331: Theory of Computing
Problem 3 (20 points)
A truth assignment M is a function that maps propositional
variables to {0, 1} (1 for true and 0 for false). We write M |= ϕ if ϕ is
true under M. We define a partial order ≤ on truth assignments
such that M ≤ M0
if M(p) ≤ M0
(p) for every propositional variable
p.
A propositional formula is positive if it only contains connectives ∧
(and) and ∨ (or) (i.e., no negation ¬ or implication →).
Use Proof By Induction to show that for any truth assignments M
and M0
such that M ≤ M0
, and any positive propositional formula ϕ,
if M |= ϕ, then M0
|= ϕ.
4 / 7
CS 331: Theory of Computing
Problem 4 (10 points)
Let Σ = {0, 1}. What language is defined by the following regular
expression? Describe that in one or two sentences.
1 (5 points) Σ
∗ 0 Σ
∗ 1 Σ
∗
.
2 (5 points) 0 0∗ 1
∗
.
5 / 7
CS 331: Theory of Computing
Problem 5 (20 points)
Let Σ = {0, 1, e, E, +, −}. Construct a deterministic finite
automaton that recognizes words of the following form
(0 ∪ 1)(0 ∪ 1)
∗
(e ∪ E)(+ ∪ −)(0 ∪ 1)(0 ∪ 1)
∗
Note that “(” and “)” are only for readability; they are not part of the
regular expression.
6 / 7
CS 331: Theory of Computing
Problem 6 (20 points)
Let A = hQ, Σ, δ, q0, Fi and B = hQ, Σ, δ, q0, F
0
i be two
nondeterministic finite automata such that F
0 = Q \ F. In other
words, the only difference between A and B is the final state set; a
state is final in B if and only if it is not in A.
Prove or disprove: The language L (B) is the complement of the
language L (A), i.e., L (B) = Σ∗
\ L (A).
Note that if the statement is true, you must provide a formal proof,
and if the statement is false, then all you need to do is describe a
counterexample.
7 / 7
CS 331: Theory of Computing