The problem: Imagine a row of n DFAs. The leftmost DFA is the "general", and all of the other DFAs are "soldiers". Each DFA is adjacent to exactly two others, one on its right and one on its left, except for the general and the rightmost soldier who are adjacent to only one other DFA. Initially, all DFAs start in their initial state. At some arbitrary point in time, the general is placed in a special state called "fire when ready", and at some time later, all soldier DFAs must switch into a "fire" state simultaneously, and this must be the first time that any of them is in the "fire" state.

Assume that there is a global clock. At each time step, each DFA may change its state. The next state of a DFA may depend only on its own current state and the current state(s) of its neighbors. The DFAs must all have the same program (that is, they are all identical DFAs), except perhaps the general and the rightmost soldier. The number of states allowed should be some constant that DOES NOT DEPEND on n, the number of DFAs in the line. More specifically, your design should consist of the description of a general DFA, a soldier DFA, and a rightmost DFA, such that regardless of the number of soldiers we line up between the general and the rightmost soldier, the squad will still function properly.

Be sure to describe in words (no DFA notation necessary) exactly how your solution works, and argue that it does in fact work. For even more fun, program your solution and generate a graphic display of instantaneous "snapshots" showing how the squad operates.

My particular implementation actually uses 23 different states, but many of those are transition states. You can see the important ones here on the right. Here's the basic theory:

  • All of the DFAs are the same, but the left one starts in the "General" state, and the right one starts in the "Rightie" state.
  • The General starts by sending two signals (one right after the other) - one that travels quickly, and one that travels slowly. Each "drone" DFA is programmed to pass the fast signal on right away, but hang onto the slow signal for two turns before passing it on.
  • The fast signal "bounces" off the right edge and heads back towards the other one.
  • Do the math - they meet in the exact center! There are two separate cases handed, depending on the parity of the number of soldiers.
  • We're almost done - now we treat each half of the squad separately, in effect "promoting" the right-center soldier to general, and promoting the left-center soldier to rightie. Both of these then send out signals to find their centers, as before. Kind of like recursion, except in parallel processing.
  • As soon as a general appears right next to a rightie (or is about to, in some circumstances), the first one to notice goes into "Fire in Two" mode. This triggers that DFA's neighbors to go into "Fire in One" mode, and the turn after that, they all go into "Fire" mode. We're assuming memory-mapped I/O, here, so the guns should all go off more or less simultaneously.

See it work!

To convince all those skeptics out there that I didn't draw the cute bathroom tile pattern on the left using SuperPaint or xpaint, I'm giving you access to a special Web version of the firing squad. Just enter the number of soldiers you would like to see (including the general and the rightie), and check the box for animation, and click Fire When Ready. If you check the Animation box, you'll see a display similar to the one at the top, and if you don't, you'll see the tiles like on the left here. Guess how many soldiers the displays on this page have?

Create your own Firing Squad!

Animation
Number of soldiers:

One last note: Though this problem can certainly be solved in fewer than 23 states, this solution is O(n) - specifically, n soldiers will always fire in fewer than 3n ticks.

Don't see anything on this page? Sorry, your browser doesn't support tables.

Don't see the animated GIFs? Sorry, your browser doesn't support the full GIF89a.

Don't know what I'm talking about? Sorry, you must not be in Theocomp this semester.

This page is entirely the work of Dominic Mazzoni. The picture of Ran was stolen without his permission from one of his Web pages. All opinions expressed or implied are not in any way supposed to reflect the views of Prof. Libeskind-Hadas or any other member of the HMC CS staff, or of the college. But that's okay, they have their own opinions and views!