A prisoner is awaiting execution by firing squad. A row of N robotic soldiers stands nearby.
These robotic soldiers can be in a finite number of states (they are all finite state machines). A clock provides a sequence of time steps: 0, 1, 2, etc.. At each step, the state of each soldier is given by a transition function. This function takes three arguments as input: the soldier's previous state, the previous state of the soldier to the right, and the previous state of the soldier to the left. The transition function must be identical for all soldiers except for the soldiers at the ends of the row, whom could have different transition functions.
One of the soldiers at one end of the row is deemed the general of the squad. Initially at time 0, the general is in state qinit, whereas all other soliders are in state qsleep. The objective is to get all soldiers to enter the state qbang simultaneously for the first time, thereby riddling the prisoner with N bullets.
Design state machines and transition functions for the robotic soldiers which will accomplish this objective, given that the number of states for a soldier cannot depend on N. What is the running time of your system in terms of N?