2. Derive the state diagram for a FSM that has an input w and an output z. The machine must generate z-1 when the previous four values of w are 1001 or 1111; otherwise, z-0. Overlapping input patterns are allowed. An example of the desired behavior is Z: 000000100100010011 3. Design a FSM that realizes a three-bit Gray-code counter, which counts in the sequence 000, 001, 011, 010, 110,111,101,100, 000