|
home—info—lectures—exams—archive
S → ε S → aSbShow how S can derive the string "aaabbb" (also known as a3 b3).
state | 0 | 1 |
s0 | s1 | s0 |
s1 | s0 | s2 |
s2 | s1 | s1 |
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.
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, where whenever a team fails, the other team gets to serve. Express your answer in table format.
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,DThe task is to come up with a pairing of each person with someone of the opposite gender.
For example, one dating company, “HappyGuys” came up with the following solution: A+W, B+X, C+Y, D+Z.
Another company, “HappyGals” arrived at a different solution: A+W, C+X, D+Y, B+Z.
In the HappyGals solution to the example given above, what happens, when Bernie+Zelda happen to go out dancing at the same club as Corky+Xena?
Finally, consider The Suitor's Algorithm (phrased in medieval, rather sexist terms):
1 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. ↩
2 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. ↩
3 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.
↩4 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 either require adding (score) counters to our FSM (at which point it's technically not a finite state machine), or we'd need to increase our states by a factor of 212 — instead of ‘Ret2’, we'd have states like ‘Ret2-while-score-is-17-to-3’, ‘Ret2-while-score-is-17-to-4’, …, Yikes! ↩
5 Two inputs are fundamentally different if you can't change one into the other just by re-naming. That is, the two inputs should not be isomorphic. ↩
home—info—lectures—exams—archive
©2008, Ian Barland, Radford University Last modified 2008.Dec.11 (Thu) |
Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu |