DFA Firing Squad --- ------ ----- Preface ------- One of the clever problems in the elementary theory of computation is the following. An army has a protocol which is equivalent to a deterministic finite automaton (DFA) that the army teaches its soldiers for use when in a firing squad. The soldiers line up, and a sergeant at one end whispers in the ear of the soldier at that end. The soldier turns and whispers in the ear of the next soldier, and so on. After a while the soldiers are all madly turning and whispering commands to their comrades, and then after this goes on for a long while, they suddenly turn as one and fire. The soldiers are running a DFA algorithm that has a left input, a right input, a left output, and a right output. But the clever part is that same DFA is use regardless of how long the line is. The line can be much, much longer than the number of states in the DFA, and the soldiers will still fire in unison. Thus no counters can be used by the algorithm. Problem ------- Fortunately your are not being asked to program the DFA. Instead you being asked to program a simulation which will allow the DFA programmer to develop the DFA program (i.e. the transition matrix), or more likely, experiment with subalgorithms. More precisely, you are to simulate a row of DFA's each with an identical transition matrix that is input to your program. The DFA's have left and right inputs and outputs attached to each other, and each DFA has an internal state. Specifically, the left(right) output of a DFA is attached to the right(left) input of the DFA's left(right) neighbor. The internal state of a DFA is represented by a lower case letter. The input and output states are represented by decimal digits. The total state of one DFA is one left output state, one internal state, and one right output state. For example, 0c3 represents a DFA state with 0 left output, c internal state, and 3 right output. The transition matrix has as input one left input state, one internal state, and one right input state. The transition matrix has as output one left output state, one internal state, and one right output state. For example, the transition from 0c3 to 1d4 is triggered when at the beginning of a cycle the left input of a DFA is 0, the internal state is c, and the right input is 3, and this transition sets the left output to 1, the internal state to d, and the right output to 4. The character `-' may be specially used as an input or output state in defining a transition. As an input state it means any value of that input state will suffice. As an output state it means that the current output state is left unchanged. Thus the transition from -c3 to 1d- will be triggered if the internal state is c and the right input is 3, regardless of the left input value. And the result of the transition will be to set the left output to 1 and the internal state to d, but leave the right output alone. In addition to the DFA's there is one left end input representing the sergeant. This starts out equal to 9 and gets set to 8 by the first cycle of the simulation. It is connected to the left input of the DFA at the left end of the line. There is also a right end input that is always set to 9, which represents the fact that the soldier on the right end of the line knows he is at the right end. It is connected to the right input of the DFA at the right end of the line. The initial state of each soldier before the first cycle is 0a0; that is, each soldier has both outputs 0 and internal state `a'. If there is no transition matrix entry that applies to a soldier during a cycle, the state of the soldier does not change during that cycle. Input ----- The input consists of any number of run descriptions. Each run description begins with three integers: the number of DFA's (i.e. soldiers) (at most 100) the number of cycles to run the simulation the number of cycles between printouts (see below) These are followed by transitions terminated by `---'. Each transition has an input description and an output description. The input description has the form: for instance: `8a-' or `8a7'. The output description as the form: for instance: `1b-' or `1b0'. The input ends with an end of file. Output ------ The first line of output for a run is a line of the format: RUN #: where # is the run number. Runs are numbered 1, 2, 3, 4, ... . The rest of the lines of the output consists of descriptions of the simulation state after some number of cycles. An example is: 5: 8 0c3 0c3 0a1 0a1 0a0 0a0 9 Each state description is a single line. The first thing in the line is the number of the cycle that has just finished; in the example this is 5. This number is an unsigned integer that is right adjusted in 5 columns, and is followed by a colon and a space character. The next thing is the state of the left end input. This is a decimal digit. Then there are the states of the DFA's, in their order in the firing line, from left to right. Each DFA state consists of three characters in the format: where the outputs are decimal digits and the internal state is a lower case letter. Lastly there is the right end input, a decimal digit. The DFA states are surrounded by single space characters. If the number of cycles between printouts is C, then there are output lines giving the simulation state after C, 2C, 3C, ... cycles. Example Input ------- ----- 5 10 3 8a- -b1 1a- -b1 --- 6 14 1 8a0 -b1 8a1 1b1 8b0 -c3 8b1 1c3 1a0 -a1 1a1 1a1 1a9 1a1 3a0 -b1 3a1 1b1 3a9 1b1 3b0 -c3 3b1 1c3 3b9 1c3 -c1 1c3 -c9 1c3 --- 7 8 1 9a0 0b1 8b1 1b1 1a0 0b1 0a1 1b0 1a1 1c1 1b0 0b1 0b1 1b0 1b1 1b1 0a9 1b0 1b9 1b1 --- Example Output ------- ------ RUN 1: 3: 8 0b1 0b1 0a0 0a0 0a0 9 6: 8 0b1 0b1 0b1 0b1 0b1 9 9: 8 0b1 0b1 0b1 0b1 0b1 9 RUN 2: 1: 8 0a0 0a0 0a0 0a0 0a0 0a0 9 2: 8 0b1 0a0 0a0 0a0 0a0 0a0 9 3: 8 0c3 0a1 0a0 0a0 0a0 0a0 9 4: 8 0c3 0b1 0a1 0a0 0a0 0a0 9 5: 8 0c3 0c3 0a1 0a1 0a0 0a0 9 6: 8 0c3 0c3 0b1 0a1 0a1 0a0 9 7: 8 0c3 0c3 0c3 0a1 0a1 1a1 9 8: 8 0c3 0c3 0c3 0b1 1a1 1a1 9 9: 8 0c3 0c3 0c3 1c3 1a1 1a1 9 10: 8 0c3 0c3 1c3 1c3 1b1 1a1 9 11: 8 0c3 1c3 1c3 1c3 1c3 1a1 9 12: 8 1c3 1c3 1c3 1c3 1c3 1b1 9 13: 8 1c3 1c3 1c3 1c3 1c3 1c3 9 14: 8 1c3 1c3 1c3 1c3 1c3 1c3 9 RUN 3: 1: 8 0b1 0a0 0a0 0a0 0a0 0a0 1b0 9 2: 8 0b1 0b1 0a0 0a0 0a0 1b0 1b0 9 3: 8 0b1 0b1 0b1 0a0 1b0 1b0 1b0 9 4: 8 0b1 0b1 0b1 1c1 1b0 1b0 1b0 9 5: 8 0b1 0b1 1b1 1c1 1b1 1b0 1b0 9 6: 8 0b1 1b1 1b1 1c1 1b1 1b1 1b0 9 7: 8 1b1 1b1 1b1 1c1 1b1 1b1 1b1 9 8: 8 1b1 1b1 1b1 1c1 1b1 1b1 1b1 9 File: soldiers.txt Author: Bob Walton Date: Sat Feb 15 04:43:18 EST 2003 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file. RCS Info (may not be true date or author): $Author: hc3 $ $Date: 2003/02/15 09:42:54 $ $RCSfile: soldiers.txt,v $ $Revision: 1.7 $