CS206 -Discrete Mathematics II
Instructor: Chitoor V.Srinivasan
PROBLEM SET 10 SOLUTIONS

  1. Has appeared in Problem Set 9.
  2. Has appeared in Problem Set 9
  3. Has appeared in Problem Set 9.
  4. Let the random variable X be the amount which A gains and let k be the amount A gets when he wins.

    displaymath160

    displaymath161

    solving for k yields k=3.

  5. Problem has been removed.
  6. The random variables are all hypergeometrically distributed. A hypergeometric distribution with  N  total items,  D  defective items, and sample size of  n , has   E(X)= nD/N According to Larsen's book page 273 Example 5.4.7, the variance is

    displaymath162

    I will give a direct proof here and then apply it to this problem.
    Since

    displaymath163

    we have

    eqnarray17

    and

    displaymath164

    we get

    eqnarray44

    Thus

    eqnarray104

    Now lets apply the formula to this problem.  N=52  and  n=13. Thus,

    displaymath165

    (a).
    tex2html_wrap_inline184

    (b).
    tex2html_wrap_inline186

    (c).
    tex2html_wrap_inline188
  7. For binomial distribution with p as the probability of success, we have  E(X) = npVar(X) = npq  and  E(X/n) = E(X)/n = np/n =p.

    eqnarray120

  8. (a).
    yes.
    (b).
    yes.
    (c).
    no. Since   tex2html_wrap_inline196   means that 2 zeroes appear together.
    (d).
    yes.

  9. (a).
    This machine has only the start state which is a trap state.
    (b).
    This machine has a start state which is also the final state, and a trap state. Every input symbol takes the start state to the trap state.
    (c).
    This machine has 3 states, the start state, the trap state, plus state A which is the only final state. There is a transition from the start state to A on input symbol a. All other transitions go to the trap state.

  10. We'll draw the transition table for the finite-state automata.
    (a).
    The transition table of the finite state automaton is the following:

    tabular131

      tex2html_wrap_inline226   is the initial state.   tex2html_wrap_inline226   and   tex2html_wrap_inline230   are final states.

    (b).
    The transition table of the finite state automaton is the following:

    tabular136

    where   tex2html_wrap_inline226   is the initial state and   tex2html_wrap_inline230   is the final state.

    (c).
    The transition table of the finite state automaton is the following:

    tabular141

    where   tex2html_wrap_inline226   is the initial state and   tex2html_wrap_inline230   is the final state. This is a non-deterministic finite state automaton.

  11. (a).
    To specify a deterministic automaton, we need to pick a start state (n ways to do this), we need to pick a set of final states ( tex2html_wrap_inline332   ways to do this), and for each of the  nk  (state,input) pairs we can go to any one of the n states. Thus, there are   tex2html_wrap_inline336   ways to pick all the transitions. Therefore the answer is   tex2html_wrap_inline338 .
    (b).
    This is the same as part(a), except that for each (state,input) pair, we can go to any of the   tex2html_wrap_inline332   subsets of states. Therefore the answer is   tex2html_wrap_inline342 .

  12. Suppose the non-deterministic finite-state automaton A has the starting state   tex2html_wrap_inline230 . Construct a new finite state automaton B from A by adding a new initial state   tex2html_wrap_inline226  . For each transition   tex2html_wrap_inline354   add the transition   tex2html_wrap_inline356   and make tex2html_wrap_inline226   a final state if and only   tex2html_wrap_inline230   is a final state. It should be obvious that B accepts the same language as A and that the start state is never revisited.