1. Recursive Synchronize: Consider a line of n identical finite state automata which in synced time steps pass messages left and right along the line. The number of states each has cannot depend on n, hence they can't "know the length of the line. Being identical, they can't know where they are positioned in the line. For example, maybe each of them has 12 states. When one is in the 3rd such state, receives the message 2 from the left and 8 from the right, then he sends the message 3 to the left and nothing to the right and go into state 9. Because there are only 12 states and each node is running the identical code, there can be at most 24 different types of messages sent or received. Note with 12 states, a node can count up to 12 but cant count higher. The format of the answer, however, is simple sentences. Do NOT give me state transitions. Neither does the answer really need code. (a) As a warm up solve the following problem. NOT RECURSIVE. The precondition is that the automata at one of the ends has been signaled to start and the one at the other end knows that it is the other end but has not been signaled to start. Each of the other automata is in its asleep state. The postcondition is that after some length of time depending only on n. the one or two automata's in the middle simultaneously know that they are in the middle. All other automata's go back to the asleep state. In the figure below, the automata marked with a 0 are the ones in the middle. Hint: The starting automata sends two messages which get relayed along the line, one which travels at speed one and one at speed. When the fast message hits the other end, the end automata bounces it back. What should c be, how is a message sent at speed, and how is the problem solved? (My answer has four sentences and does not give anything that looking like code or DFA state transitions. Neither does it worry about n plus or minus c details such as whether there is one or two guys in the middle.) xxx Oxxx xxx00xxx (b) Recursive Fire Squad: The precondition is the same as in the previous question. The postcon- dition is that after some length of time depending only on n, all automata simultaneously go into the fire state. Design a recursive algorithm for this (as emphasized in step2). (My answer has twelve sentences and does not give anything that looking like code or DFA state transitions.) (c) How much time is there from when the left most automata is signaled to start and when they all fire? Be careful to note that some of actions happen in parallel. 1 1. Recursive Synchronize: Consider a line of n identical finite state automata which in synced time steps pass messages left and right along the line. The number of states each has cannot depend on n, hence they can't "know the length of the line. Being identical, they can't know where they are positioned in the line. For example, maybe each of them has 12 states. When one is in the 3rd such state, receives the message 2 from the left and 8 from the right, then he sends the message 3 to the left and nothing to the right and go into state 9. Because there are only 12 states and each node is running the identical code, there can be at most 24 different types of messages sent or received. Note with 12 states, a node can count up to 12 but cant count higher. The format of the answer, however, is simple sentences. Do NOT give me state transitions. Neither does the answer really need code. (a) As a warm up solve the following problem. NOT RECURSIVE. The precondition is that the automata at one of the ends has been signaled to start and the one at the other end knows that it is the other end but has not been signaled to start. Each of the other automata is in its asleep state. The postcondition is that after some length of time depending only on n. the one or two automata's in the middle simultaneously know that they are in the middle. All other automata's go back to the asleep state. In the figure below, the automata marked with a 0 are the ones in the middle. Hint: The starting automata sends two messages which get relayed along the line, one which travels at speed one and one at speed. When the fast message hits the other end, the end automata bounces it back. What should c be, how is a message sent at speed, and how is the problem solved? (My answer has four sentences and does not give anything that looking like code or DFA state transitions. Neither does it worry about n plus or minus c details such as whether there is one or two guys in the middle.) xxx Oxxx xxx00xxx (b) Recursive Fire Squad: The precondition is the same as in the previous question. The postcon- dition is that after some length of time depending only on n, all automata simultaneously go into the fire state. Design a recursive algorithm for this (as emphasized in step2). (My answer has twelve sentences and does not give anything that looking like code or DFA state transitions.) (c) How much time is there from when the left most automata is signaled to start and when they all fire? Be careful to note that some of actions happen in parallel. 1
