Harvard University
Computer Science 121 Problem Set 3 Tuesday, September 30, 2014
Problem set by **FILL IN YOUR NAME HERE**
Collaboration Statement: **FILL IN YOUR COLLABORATION STATEMENT HERE (See the syllabus for information)**
PART C (Graded by Aaron)
PROBLEM 5 (1+1+1+1+1+1 points, suggested length of 1-2 sentences of justification) Classify the following sets as finite (in which case state the cardinality), countably infinite, or
uncountably infinite. Give a brief justification. (A complete proof is not necessary.)
(A) {∅}
(B) The set of syntactically valid computer programs in the programming language Python. (C) Q × Q (where Q is the set of rational numbers)
(D) {S⊆N:allnumbersinSareprime}
(E) The set of all irrational numbers.
(F) The set of all languages over {a, b, c} of strings of exactly 50 symbols.
Solution.
(A) Finite of size 1.
(B) Countably infinite. Every Python program is just a string; since the set of all strings is countable, so is the subset of strings that are Python programs. Python programs can be arbitrarily long, so the set is infinite.
Now we show that a subset of a countable set is countable. Let A ⊆ B with B countable. Assume that A is non-empty (otherwise the result is trivial) and fix some x0 ∈ A. Then there exists an onto function f : N → B (see the last proposition in Lecture 6). Define f′ : N → B by
f′(n)=f(n)iff(n)∈A and f′(n)=x0 iff(n)∈/A. Then f′ is onto, whence A is countable.
(C) Countably infinite. Q is countably infinite (Section 3 Exercise 2.1 part 3 or Sipser Example 4.15). We can express Q × Q as a countable union of countable sets:
Q×Q= {q}×Q. q∈Q
Thus Q × Q is countable. Since it contains the infinite set {0} × Q, it is infinite.
(D) . Uncountable. The set of prime numbers P is countably infinite, thus the powerset is uncount- able. That is, there is a bijection between P and N, so there is also a bijection between P(P) and P(N). Since P(N) is uncountable, so is P(P).
(E) The set of irrational numbers is uncountably infinite. We saw in section that R is uncountably infinite and that Q is countably infinite; furthermore that R is the union of Q with the set of irrational numbers. So if the set of irrational numbers was countably infinite, R would be countably infinite–a contradiction.
(F) This set is finite with cardinality of 2350 . There are 350 strings of length exactly 50, as each symbol may be either an a, b, or c. A language is any subset of the set of all these strings, meaning there are 2350 such languages.
PROBLEM 6 (10 points, suggested length of 1/3 page)
Show that for any deterministic finite automaton M = (Q,Σ,δ,s,F), M accepts an infinite lan-
guage if and only if it accepts some string of length greater than or equal to |Q| and less than 2|Q|.
Solution.
First let’s prove that if a DFA M accepts a string of length greater than or equal to |Q| and
less than 2|Q|, then M accepts an infinite language. Suppose that M accepts a string w where
|w| ≥ |Q| and |w| ≤ 2|Q|. Since |w| ≥ |Q|, when the DFA reads w it must pass through at least
|Q| + 1 states. By the pigeonhole principle, then, there is at least one state q in which the DFA
enters twice on its computation on w. Thus we have (q, yz) ⊢mM (q, z) for some x, y, z ∈ Σ∗ such
that w = xyz,y ̸= e,m > 0. But then by the law of unread input, we also have (q,z) ⊢0M (q,z),
(q, yyz) ⊢2m (q, z), (q, yyyz) ⊢3m (q, z), etc. Intuitively, we can take the loop from state q to state MM
q an arbitrary number of times, each time creating a different string that is in L(M). Therefore, M accepts an infinite language.
Now suppose that M accepts an infinite language. First suppose that it accepts no strings of length greater than or equal to |K|. This is clearly not the case, because then it would accept only a finite number of strings, but M accepts an infinite language. Now suppose that M doesn’t accept any strings of length |K| ≤ n < 2|K|. Because L(M) is infinite, it must accept strings of length greater than |K|, so under the assumption that M doesn’t accept any strings of length |K| ≤ n < 2|K|, M must accept a string w where |w| ≥ 2|K|. However, by the pigeonhole principle, when computing on w, M must pass through at least one of its states twice, that is, (q, yz) ⊢mM (q, z) for some x,y,z ∈ Σ∗ such that w = xyz,y ̸= e,m > 0. Thus, by the reasoning above, xz must also be ∈ L(M ). Let (q, y) ⊢mM (q, e) be the smallest such cycle that M encounters in its computation on M. Thus |y| must be smaller than |K|, or by the pigeonhole principle there would have been a smaller cycle. Thus, there are two alternatives for the size of xz. Either |K| ≤ |xz| < 2|K| or |xz| ≥ 2|K|. If |xz| ≥ 2|K|, then we can repeat the same process as before as many times as necessary until we get a string v such that |K| ≤ |v| < 2|K|, because all strings longer than 2|K| must have at least one loop (in fact, they all must have more than one loop), and the substring we are removing each time is smaller than |K|, so there is no way this process will cause us to jump from a string of size 2|K| to one smaller than |K|. Thus, if M accepts a string w of length 2|K| or greater, which it must because it accepts an infinite language, then it must also accept a string v where |K| ≤ |v| < 2|K|.