State machines For each of the specifications below give a state machine for the sequential circuit. Be sure to:

• minimize the number of states in your machine,
• draw the state diagram, and
• identify the initial state.

1. (6 points) Design a sequential circuit which recognizes the sequences 0111 or 1001 on a synchronous input, x. That is, your circuit should have one output signal which is high only when the last 3 inputs and the current input are 0111 or 1001. The output (z) is shown below for a sequence of inputs (x).

    x 0 0 1 1 0 0 1 1 1 0 0 1 0 1 1 0 0 1 1 1 1 1 1 0 0 1 0 . . . . . z ? ? ? 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 . . . . . 

   The output during the initial 3 inputs can be either 0 or 1. Note that the sequences may overlap, so for example 1001110 would produce output 0001010.)

2. (6 points) Design a sequential circuit with one synchronous input x and one output z. The output z is high whenever the input sequence has at least two 1's followed by at least three 0's. The output should go high on the third 0 and remain high until the next 1. Below is a sample sequence of inputs and the corresponding outputs at the positive clock edges.

   x 1 0 0 0 1 1 0 0 0 0 1 1 1 0 0 1 0 0 0 1 1 1 1 0 0 0 0 0 1 1 0 0 0 ... z 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 ... 

3. (6 points) Design a sequential circuit which has one synchronous input x and one output z. The output is high whenever the input sequence 01111 occurs. The output should be high on the fourth 1 and should remain high until the next 0 input. The output (z) is shown below for a sequence of inputs (x)

    x 1 1 1 1 0 1 1 1 1 1 1 0 0 1 0 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 0 0 ... z 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 ...