COMS 331: Theory of Computing, Spring 2021 Homework Assignment 10
Due at 10:00PM, Wednesday, April 21, on Gradescope.
Problem 69 can be found in your textbook Automata and Computability by Dexter Kozen.
A (finite, undirected) graph is an ordered pair G = (V,E), where V is a non empty finite set of
vertices, and E is a finite set of 2-element subsets of V , called edges. For example,
denotes the graph G = (V,E), where V = {1,2,3} and E = {{1,2},{2,3}}.
Without loss of generality, we can assume that the vertex set of a graph is always of the form Vn = {1,2,…,n}, where n ∈ Z+. We can also, for each n ∈ N, define the standard enumeration e1,e2,…,e(n2) of all 2-element subsets of Vn to be the enumeration first in order of the least element
of the 2-element subset, then in order of the greater element. Thus, for example {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}
is the standard enumeration e1, …, e6 of the 4 = 6 2-element subsets of V4. A graph G = (Vn, E) 2
is thus completely specified by the binary string
xG = b1b2…b(n2) ∈ {0, 1}(n2)
defined by
1 ifek∈E bk= 0 ifek∈/E
for all 1 ≤ k ≤ n. We call xG the standard encoding of the graph G. 2
1
Problem 64. (a) Find the standard encoding xG of the following graph G.
(b) Draw the graph G whose standard encoding is xG = 0110011010.
A path in a graph G = (V, E) is a sequence p = (v0, v1, …vl) of vertices vi ∈ V such that, for every 0≤i
2
(d) Prove that, for all sufficiently large n ∈ N, every graph G = (Vn, E) with C(xG) ≥ n − 2 n
25
has diameter 2.
(e) For each n ∈ N, suppose that we choose a graph G = (Vn, E) at random by using independent
tosses of a fair coin to decide whether each of e1,…e(n2) is an element of E. Prove that, for all sufficiently large n ∈ N,
−2n Prob[diam(G)=2]>1−2 5 .
Let p0, p1, p2, … be an enumeration of all prime numbers in order. Thus p0 = 2, p1 = 3, p2 = 5, etc. An important number-theoretic fact is that every integer n > 0, there exist m ∈ N and a0, …, am ∈ N such that
n = pa0 pa1 …pam . 01m
Problem 67. For each m ∈ N, let
F = {pa0pa1…pam |a ,…,a
(∗)
p0, …, pm.
(a) Prove that there is a constant c ∈ N such that, for all m ∈ N and n ∈ Fm,
C(n) ≤ 2(m + 1) log (1 + log n) + m + c.
(b) Use part (a) of this problem to prove that there are infinitely many prime numbers.
Problem 68. Design an NFA that accepts the language
L = {w ∈ Σ∗ | w contains at least three 0’s, or exactly two 1’s}.
Problem 69. Page 302 #1 (convert an NFA to a DFA using subset construction).
Problem 70. Provide an example that if N is an NFA, swapping its accept and non-accept states does not yield an NFA that recognizes L(N) where L(N) is the complement of L(N).
∈ N}
be the set of all positive integers that can be factored as in (∗) using only the prime numbers
m01m0m
3