Due Nov.30 (Fri) 17:00

(But do look at #6 and think about it before lecture, if possible.) Consider the grammar with production rules 
S → ε
S → aSb
Show how S can derive the string "aaabbb" (also known as a b).
Your answer will be of the form S ⇒ ⇒ ⇒ … ⇒ "aaabbb".
(Recall that ε represents the empty string; Rosen uses λ for this same purpose.) S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaabbb Some extra credit: prove that the preceding grammar can generate all strings of the form a b, for all n∈N. Proof by induction: Let P(n) be S ⇒* aSb. Base case, n=0: With no productions at all, we derive S = aSb. Inductive step: ∀k≥0, P(k)→P(k+1).
If we know (by P(k)) that S ⇒* aSb, then applying the rule S⇒aSb just more we get S ⇒* aSb ⇒ aaSbb = ak+1Sbk+1, as desired. Thus we know ∀n.P(n). Finally, we can apply the rule S⇒ε to get that ∀n, S⇒*a b.
Why does this proof not show that the grammar generates exactly the language L' = { a  b | n∈N} ? While the grammar does generate exactly that language, we didn't prove it; we only shows L' ⊆ L(G). We neglected to try to prove that L(G) ⊆ L'. Draw the finite-state machine described by the following table:
state 0 1 s s s s s s s s s 
        1
      /--\
      |  |
      V  |
    +------+   0   +------+    1  +------+
    |      |<------|      |<------|      |
    |  s0  |       |  s1  |<---0--|  s2  |
    |      |------>|      |------>|      |
    +------+   0   +------+    1  +------+
This FSM doesn't seem to have any obvious purpose. For the finite state machine drawn to the right, ignoring the second number on each arrow Rosen takes the second number to be the output for that transition. In the version of FSMs discussed in class, we didn't include any output, instead thinking of the current-state as conveying meaning. What state is the machine in, after the input sequence    "00110101"? s What state is the machine in, after the input sequence "0100110101"? s Describe the set of all strings which leave the machine in state s. Strings with an even number of 0s, and an odd number of 1s. Remember that for each input sequence, we start from the machine's start-state, s.

We'll model the progression of a volleyball game with a finite state machine. 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-return
We'll consider a return as a single event, and not model how it might be made up of up to three individual hits by one team. Clearly, you could certainly model the up-to-three hits by refining your FSM, though it might need inputs (the ref) distinguishing between a hit which wasn't a return but wasn't drop-the-ball either.
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, where whenever a team fails, the other team gets to serve. Express your answer in table format. state Succeed Fail Srv1 Ret2 Srv2 Ret1 Ret2 Srv2 Srv2 Ret1 Srv1 Ret2 Ret1 Srv1
  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

    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, for our purposes, once a re-serve resolves, the botched serve is forgotten; thus there can be a re-serve every single volley.

    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!

    We'll need to replace Srv1 with two states — whether its the first serve attempt, or the second. Call these Srv1a and Srv1b. (Similarly for Srv2, of course.)

    (Here's the table form of the answer, although the graph is what you were asked for) state Succeed Fail Srv1a Ret2 Srv1b Srv1b Ret2 Srv2a Ret1 Ret2 Srv2a Srv2a Ret1 Srv2b Srv2b Ret1 Srv1a Ret2 Ret1 Srv1a

  3. Scoring in volleyball is interesting: only the team which served may score a point Well in real volleyball, there are apparently "rally points" in overtime, a mode where every play results in somebody getting a point. You can see that we could also model this, but it would require a referee input telling us to switch into rally mode, and would also mean a bunch more states. Modify our FSM to handle this. (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.

    We'll add states IncScore1 and IncScore2. In addition, during a volley (Ret1 and Ret2), we need to keep track of which team served . We'll call these Ret1a (meaning team1 served) and Ret1b (meaning team 2 served).

    (Here's the table form of the answer, although the graph is what you were asked for) state Succeed Fail Srv1a Ret2a Srv1b Srv1b Ret2a Srv2a Ret1a Ret2a Srv2a Ret1b Ret2b IncScore2 Srv2a Ret1b Srv2b Srv2b Ret1b Srv1a Ret2a Ret1a IncScore1 Ret2b Ret1b Srv1a IncScore1 Srv1a - IncScore2 Srv2a -
    So, for example, state Ret1a means that team1 is returning, and that team1 had served. If they fail, then nobody scores a point, but we go to Srv2a. On the other hand, state Ret1a means that team1 is returning, and that team2 had served. If they fail, then team2 scores a point.

Consider the Marriage Problem. Here is one example input: Four men (Alistair, Bernie, Corky, Dweezil -- abbreviated A,B,C,D resp.), and four women (Winnie, Xena, Yolanda, Zelda -- abbreviated W,X,Y,Z resp.), along with their preferences for hooking up marriage: 
Alistair:  W,X,Y,Z
Bernie:    W,X,Z,Y
Corky:     W,Y,Z,X
Dweezil:   X,W,Y,Z

Winnie:    A,B,C,D
Xena:      C,B,D,A
Yolanda:   D,B,A,C
Zelda:     C,B,A,D
The task is to come up with a pairing of each person with someone of the opposite gender.

For example, one dating company, HappyGuys might come up with: A+W, B+X, C+Y, D+Z.

Another company, HappyGals tried: A+W, C+X, D+Y, B+Z.

Give an input with two men and two women, along with all possible solutions to your input. With men A,B and women Y,Z we could have inputs: 
        A: Y,Z
        B: Z,Y

        Y: A,B
        Z: B,A
There are only two possible solutions: {A+Y,B+Z} and {A+Z,B+Y}. Give a second (fundamentally different) input with two men and two women. Like the previous, except that the men will have different preferences: 
        A: Z,Y
        B: Y,Z

        Y: A,B
        Z: B,A
There are still only two possible solutions: {A+Y,B+Z} and {A+Z,B+Y}.

In fact, with two men and two women, there are is only one other fundamentally different input: 

        A: Y,Z
        B: Y,Z

        Y: A,B
        Z: A,B
All other inputs merely involve swapping the names A,B and X,Y (or both).

In the HappyGals solution to the example given above, what happens, when Bernie+Zelda happen to go out to the same restaurant as Corky+Xena?

Chloe realizes she'd prefer Zorba to her date, and winks. Zorba realizes he'd prefer Chloe to his date, and winks back. C+Z leave together! To think about for lecture: Are some solutions better than others? What are good properties for a solution to have? How many solutions are possible, for an input with 2n people? Is a brute-force solution feasible?

Finally, consider The Suitor's Algorithm (phrased in medieval terms): male strategy: go to the tower with his most-preferred woman who hasn't already spurned him, and stay as long as he's being flirted with. female strategy: sit in her tower, and of all the suitors outside her window (if any), flirt with the highest preference, and spurn the rest. This repeats until there are no changes. We will talk about this algorithm in lecture, starting with the question of whether or not it is guaranteed to terminate.

Lemma: If a woman A is flirting with a man M, and she eventually ends up with some man N (perhaps M=N), then she'll end up with N such that pref(A,A*) >= pref(A,M). Lemma: a man Z will never re-visit a tower he has previously left. Questions: - does this algorithm terminate? (Argue why there won't be some loop that goes on forever.) Yes: [why?] At each step, a woman's preference will stay the same or go up (never down). It can only go up a maximum of n times. If Alternately: Each man will move no more than n times, and there aren't any Note how our proof gives a bound on the running time. - When this algorithm stops, does it give a solution? That is, does every woman's tower have exactly one man at it? Yes -- if k+1 men are visiting a tower, then (by the alg) k will move on. By counting, if n men are assigned to n towers and none of them have 2 or more, then each must have exactly one. - is it guaranteed to produce a stable solution? Yes: Proof by contradiction: Suppose not; suppose that after a solution is reached, some couple A,Z would prefer to break out of the solution. In that case, Z visited A's tower (before the person he ended up with). But then A must have spurned Z, meaning she had some better catch M dangling on the line. So her final catch A* must at least as good as M, who was better then Z. So she would not want to swap with Z, contradicting our premise that A+Z would both prefer each other to their solution. Optimal solution? "The highest rank choice out of all stable solutions" - For men: Let t be the first round where some man is rejected by his optimal mate. Call Z's highest choice (out of all *stable* solutions) is opt(Z). Clearly, in the suitor's alg , Z won't end up with anybody higher than opt(Z). Suppose at some point, he visits opt(Z)'s tower. But some other man Y is there, and opt(Z) chooses Y over Z. (Note that if Y shows up at that tower, it's because he was spurned by all his higher choices, and Y can't be with any of those women higher choices in a stable solution.) Well then, We Want: Lemma: if a man is spurned during suitor's alg, then no *stable* solution exists where he is with that woman. Proof by contradict: Suppose Z is spurned by A (because of Y), and yet there is some stable sol'n which includes Z+A and Y+B. where A: ..., Y, ..., Z, ... Then in order to be stable, we must have Y: ..., B, ..., A, ... [If not, it wouldn't be stable: A+Y] But then the only way the Suitor's Alg would have Y visit A is if B had spurned him: B: ..., X, ..., Y, ... even those Suppose Z is spurned by A at some step, due to Y. Let B be any person with Z in a stable matching. A: ..., Y, ..., Z, ... Y: ..., A, .... Z: ..., A, ..., B, .... Suppose that Z is eventually matched Meaning A+Y both prefer each other to Z+whomever-Z-will-end-up-with. by induct on time-step -- each man at time k is What data types would you use to represent an input to the problem? (Be as abstract as possible, of course; we don't want to tie the hands of any implementors.)

Sets M and F (males and females), where they are the same size and disjoint (|M|=|F| and M∩F = φ).

Each person's preference is a functions p: M→F and p:F→M where n = |M|=|F|. (Note that F means F✗F✗F✗...✗F, n times.)

Actually, we can be more precise, since people can't be repeated in a preference list; each person has in mind a permutation of the other gender: p : M→π(F) and p : F→π(M)

A solution is a matching function: s : M→F, s : F→M.