CS373 – Fall 2003 - NMG
September 5, 2003
Homework Assignment 1 – Problem 9 omitted 9/9/03, prob. 10 fixed
Due Friday 9/12/03 after class
Problem set for chapter 1 (total of 90 points):
The problems are weighted as shown
All steps must be shown. The three basic steps for inductive proofs must be explicitly shown
Problem 1 (10 points) Let f be a function on the natural numbers satisfying:
f(n) = 0, if n = 0
f(n) = 4f(n/2), if n is even and n > 0
f(n) = f(n-1) +2n-1 if n is odd
Using strong induction prove that f(n) = n2 for all n 0.
Hint on strong induction:
As before, show the basis step that P(0) is true. We now have a somewhat different inductive assumption: “assume p(0), p(1), ..., p(n) is true” and from this assumption prove that p(n+1) to be true. Note that the inductive assumption is now a sequence of propositions including the basis. Now we can use any of the propositions in the inductive assumptions to imply the n+1 case, rather than being restricted to only the nth case. In some cases relating the n+1th case to the nth case may not be easy. The hint is that it is sufficient to relate the n+1 case to any one of the p(0), p(1), ..., p(n) cases - not necessarily the nth case, ie., if you can show that that the n+1 case is expressed in any one of these cases then you could invoke the inductive assumption. This is formally known as “strong” induction or “The Second Principle of Induction” - easier than ordinary induction (relating n+1 only to n). Note that it can be shown that ordinary and strong induction is equivalent.
Problem 2 (5 points): Strong induction was used erroneously to prove that 2n = 1 for all n 0. Show what is wrong with the following “proof ” (or if you prove it correct, maybe you’ll get the Nobel Prize in mathematics):
BASIS STEP: 20 = 1 by definition (a0 = 1 for any a).
INDUCTIVE ASSUMPTION: assume that 2k = 1 for all 0 k n, ie., assume 20, 21, 22, … , 2n are all equal to 1 for any n 0
INDUCTIVE STEP: 2n+1 = (2n)(2n) / (2n-1) by the rules of exponents (“/ ” means “divide by”).
But both 2n and 2n-1 fall within the range of the inductive assumption and may be replaced 1.
Thus 2n+1 = (1)(1)/1 = 1. Hence having “proved” the (n+1)th case, we conclude that 2n = 1 for all n 0. QED!
Problem 3 (10 points)
Let T be a strictly binary tree ie., each vertex has precisely two children, except for the leafs which have no children. Assuming that the root and leafs count as vertices, prove that if T has n leafs, then the number of vertices, N, in T is exactly N = 2n-1. Use induction on the number of vertices, N in T. Hint: a strictly binary tree T can always be made up of the root of T and two “subtrees” each having roots consisting or the two vertices coming off the root of T. The sum of the leafs in the two subtrees add up to the number of leafs in T and the sum of the vertices in the subtrees plus 1 is the number of vertices in T.
Problem 4(20 points, 5 points each)
Prove or disprove the following without resorting to “membership” or “truth” tables.
Assume A, B and C are sets, and the “apostrophe” ( ‘ ) means “Complement”.
Remember that “if and only if” proofs require you to prove the implication in “both directions”.
Tip: to prove A = B, you must show that A B and B A.
(a) A B, if and only if 2A 2B … try proof by contradiction for the 2A 2B ==> A B part. Assume A, B, and C are finite.
(b) Prove that 2(A B) = 2A 2B
(c) Prove that A – (B A) = A - B .
(d) Prove DeMorgan’s Law: (A B)’ = A’ B’ by proving that each side is a subset of the other side.
Problem 5 (5 points): The symmetric difference of A and B, denoted by A B is the set containing those elements in either A or B, but not in both A and B (analogous to exclusive OR in logic).
Using a proof by contradiction, prove that if A B = A then B = .
Problem 6 (5 points) By doing some sample derivations and giving a convincing informal argument, determine whether or not the following two grammars are equivalent (generates the same language):
Productions for grammar 1:
S aS | A
A bA |
B aA
Productions for grammar 2:
S AB
A aA |
B bB |
Where, in both grammars: T = = {a, b}, V = {S, A, B}and the start symbol is S.
In set theoretic notation, define the language generated by each (or both if equivalent).
Problem 7 (10 points): Given = {a}. Find a grammar that generates the following language:
L = {w : |w| mod 5 < |w| mod 3}.
Problem 8 (5 points) Given the grammar: G = (V, T, S, P) with
V = { S, R, A, B }
T = {a, b, [, ]}
P: S -> aR[a] | bR[b] | [ ]
R[ -> aR[A | bR[B | [
Aa -> aA
Ab ->bA
Ba -> aB
Bb -> bB
A] -> a]
B] -> b]
Informally determine the language that this grammar generates by deriving a sample string of eight terminal symbols and then convincingly generalize to a definition of the language generated.
Problem 9 (10 points): - Problem 9 has been omitted.
Problem 10: (10 points)
Design a transducer that accepts bit strings a1 a2 a3 … and computes the binary value of each set of three consecutive bits modulo 5. More specifically, the transducer should produce m1, m2, m3, …, where
m1 = m2 = 0
mi = (4ai-2 + 2ai-1 + ai) mod 5, i = 3, 4, …, where the last bit received (ai) is the least significant bit.
Hint: Read Section 1.3, and review the solved problem 1.3.11 should give insights into this problem. You mayassume that the transducer has five possible outputs: 0,1,2,3,4. Each transition will have one of these outputs
Problems from: Linz, Sect 1.2: Prob. 13 - 3rd ed. (11 - 2nd ed.) (parts b, c, e) (10 points, (4,3,3 points each)), Drill time! – these are for the most part are “standard” stock problems whose solutions may appear in various sources – I have most of the sources! So no credit if the solutions appear to be direct copies. It behooves you to have a thorough understanding of the solutions (show me that you understand the problem). In problems e, f, g, and h you may symbolically use the results of parts b and c by letting s1 and s2 be the starting symbols for parts b and c respectively, and letting S be the starting symbol for parts e, f, and h.
CS373 Homework assignment 1 Fall 2003 Page 1