1. Derive the state diagram for an FSM that has an input w and an output z. The machine has to generate z=1 when the previous three values of w were 011 or 111; otherwise, z=0. Overlapping input patterns are allowed an example of the desired behavior is w: 010111100110011111 z: 000011100010001111