Hw12: FSM

Before you tackle the homework, remind yourself of our general hw policies. Clarifications shown in purple.

1. (0pts) Make sure that the grade database has your correct scores, up through hw09, as of Apr.18 (Friday) 19:19.
   See TA or prof office hours with any discrepancies.
2. (0pts) Pick up any unretrieved homeworks (room number on Homework page).
3. (4pts) Show that the converse of Th'm 5 (Section 5.3) (4ed: Section 4.5 th'm 3) does not hold.
   Hint: a uniform distribution will suffice, but choose a sample space of size three; two is too small.
   (Recall that random variables are just functions from the sample space to R, and that the product of two functions (f*g) is the function (lambda x. f(x)*g(x)).)
4. (8pts) We'll model the progression of a volleyball game with a finite state machine (as per notes). Our first attempt will be overly simplistic, but we'll add some features to arrive at a slightly less simplistic version.
   1. Let the set of states be
      S = { team1-to-serve, team1-to-return, team2-to-serve, team2-to-return }.
      (You can abbreviate these Srv1,Ret1,Srv2,Ret2.) Let the inputs be the set I = {Succeed,Fail} (you can abbreivate S,F), indicating a ref's call¹ that the current state's action just succeeded or failed, resp. Thus we think of our model proceeding along the lines of:

      state:  team2-to-serve
      input:    Succeed         [indicates team 2 served successfully.]
      state:  team1-to-return2
      input:    Fail            [oops, team 1 failed to return the ball.]
      state:  team-2-to-serve
      ...
      

      Specify the 4-state FSM best modeling a volleyball game. Express your answer in table format.
   2. Give a new FSM which allows for the possibility of a "re-serve": If a team is to serve but fails, they get one further attempt³ before losing possession. You will need to add a little more state.
      Express your answer as a picture of a directed graph with labeled edges (as in lecture, similar to Rosen 11.2). Neatness improves clarity!
   3. Scoring in volleyball is such that only the team which served may score a point⁴. Our FSM won't actually keep track of score, but it will indicate when one team or the other scores a point, via two new states "increment-team1-score" and "increment-team2-score". (After an increment, the referee will always give the input S.)
      This requires quite a few more states. Don't write down the answer for this part -- instead, just include your answer as part of the next subproblem.
   4. Currently, our FSM models a volleyball game that never ends. We'll modify this by letting the referee keep score, and (after a team's score is incremented) they'll give the input "S" to continue the game, and "F" to indicate that that team just won.
      Express your answer as a graph, as before.

³ This was how we played in my (dreaded) junior high PE; however more competitive volleyball might only allow re-serves when the serve hit the net; I'm not sure.

Regardless, Once a re-serve resolves, the botched serve is forgotten; thus there can be a re-serve every single volley.