CSCI 2200 Foundations of Computer Science (FOCS) RPI 2014 ASSIGNMENT 9 1 Warm Up (do before recitation lab) (1) A = {a, b, c}; B = {x, y, z}. Consider the function f : A 7→ B with f (a) = x; f (b) = x; f (c) = z. Circle which (if any) of the following that correctly describe f : an injection a surjection one-to-one a bijection invertible (2) For the finite automaton shown the input is a string over Σ = {0, 1}. Answer the questions posed. 0 (a) What is the start state? 1 s1 (b) What is the set of accept states? s2 0 (c) What sequence of states are followed for input 0011? 1 1 (d) Does the machine accept 0011? 0 s3 (e) Does the machine accept ǫ (the empty input)? s4 0 (f) Give strings of length 1,2,3,4,5,6 that the machine accepts. 1 (3) Give an automaton that accepts quarters and dispenses a coke each time the machine gets 3 quarters. (4) Give an automaton that takes quarters and dimes and dispenses a candy whenever it has at least 50c. (5) Give a finite automaton to accept the language L = {00010, 10111} (6) Give a finite automaton to accept the language L = {strings containing 101 as a substring} 2 Recitation Lab (TA will work these out in lab) (1) Show that {positive multiples of 5} ⊂ N, yet it is countable and has the same cardinality as N. (2) Show that the set of all infinite binary strings is uncountable. (3) Show that the set of all finite binary strings is countable. (4) Give a DFA that accepts the language L = {0012n |n ≥ 0}. (5) Give a recursive definition of the language in recitation problem 4. (6) Consider the coin flipping game which tosses a fair coin and stops when you get HH. Define the language H over the alphabet Σ = {H, T } to contain the strings which end at their first occurrence of HH: H = {w|w = xHH, x does not end in H or contain HH as a substring}. Give the deterministic finite automaton that accepts this language. (When you add probabilities to the transitions and solve the recurrence for P (n), the probability to be in the accept state at toss n, you obtain the solution of recitation Problem 6 in Assignment 8.) 1 3 Problems (hand these in) For all these problems, n ∈ N = {1, 2, 3, . . .}. (1) Answer YES or NO, and explain your reasoning. “Is the correct answer to Question (1) ‘NO’ ?” (2) Give a DFA that recognizes the following language over the binary alphabet: L = {w|w does not contain the substring 010}. (3) (a) Let Z2 be the set of pairs {(z1 , z2 )|z1 , z2 ∈ Z}. Show that Z2 is countable. (b) Let Q be the set of rational numbers, Q = {r|r = ab , a ∈ Z and b ∈ N}. Show that Q is countable. (c) Let F be the set of all functions from N to N, F = {f |f : N 7→ N}. Show that F is uncountable. (4) Consider the sample space S = {1, 2, . . .} = N and random variables X(n) = n and Y (n) = n2 . (a) For the probability function P (n) = 2−n , compute E[X] and E[Y ] and var[X]. ∞ ∞ P P [Hint: Show that nan = a/(1 − a)2 and n2 an = a(a + 1)/(1 − a)3 for 0 ≤ a < 1.] n=1 n=1 (b) How is var[X] related to E[X] and E[Y ]? (c) Use the Markov and Chebyshev bounds get an upper bound on P[X ≥ N ], for N > 1. Now compute the exact value of P[X ≥ N ] and compare your 3 answers. 6 (d) For the probability function P (n) = 2 2 , compute E[X]. π n (5) N people toss their hats in the air (N is even). The hats land randomly on their heads. Let X be the random variable which is the the number of people who get their hats back. (a) Compute E[X] and var[X]. [Hint: Define another random variable xi = 1 if person i gets their hat back and xi = 0 otherwise. How is X related to the xi ? Are the xi independent?] (b) Give an upper bound on the probability that more than half the people get their hats back. A lawyer had never won a case. He decided to quit practicing law but before he did so he declared that he would file his last case against his law school, sueing for a refund of his tuition. Lawyer to Judge: “My argument is iron-clad: they did such a bad job that I never won a case.” Judge (pondering): “Hmm. . . , very reasonable. If you never win a law suit, you certainly deserve a refund.” Nevertheless, the judge pondered forever and never made a ruling for fear of contradiction. 2 /