Sequential Machines

The machine has one serial input X and one output Y. Y = 1 when the last three bits received are 1, 1, 0.

A Mealy machine is used (output depends on the present state and the present input), and overlapping sequences are detected. Since the sequence has 3 bits, 3 states are needed, so 2 JK flip-flops ($Q_1Q_0$) are used, clocked on the positive edge. (A Moore machine would need 4 states.)

Step 1: States

Step 2: State diagram

 Main path (label = X/Y):
 A -1/0-> B -1/0-> C -0/1-> A
 Other transitions:
 A -0/0-> A    B -0/0-> A
 C -1/0-> C

Step 3: State assignment

Code 11 is unused and is treated as a don't care.

Step 4: Excitation table

JK excitation: 0→0: J=0, K=X; 0→1: J=1, K=X; 1→0: J=X, K=1; 1→1: J=X, K=0.

Step 5: K-maps (rows $Q_1$, columns $Q_0X$)

Step 6: Equations

$$\begin{aligned} &J_1 = Q_0X,\quad K_1 = \overline{X} \\ &J_0 = \overline{Q_1}X,\quad K_0 = 1 \\ &Y = Q_1\overline{X} \end{aligned}$$

Step 7: Logic diagram

   +-----+       +-----+
J0>|J   Q|-Q0 J1>|J   Q|-Q1
   | FF0 |       | FF1 |
K0>|K    |    K1>|K    |
   +--^--+       +--^--+
      |             |
CLK---+-------------+
X = serial input, common to the gates
J1 = Q0.X   K1 = X'
J0 = Q1'.X   K0 = 1
Y = Q1.X'

The gates for each flip-flop input are built from the equations; the output gate gives Y directly (Mealy output).

Unused state 11: with the equations above, from 11 the machine goes to 00 when X = 0 and to 10 when X = 1, so it enters the valid states after one clock. Since Y can be 1 from state 11 for one clock, the flip-flops should be cleared to 00 at power-on (reset).

Check with an input stream

Y = 1 appears exactly on the clock in which the last bit of 110 arrives; overlapping sequences are also detected.

The machine has one serial input X and one output Z. Z = 1 when the last four bits received are 1, 1, 0, 1. Only SR flip-flops are used.

A Mealy machine is used (output depends on the present state and the present input), and overlapping sequences are detected. Since the sequence has 4 bits, 4 states are needed, so 2 SR flip-flops ($Q_1Q_0$) are used, clocked on the positive edge. (A Moore machine would need 5 states.)

Step 1: States

Step 2: State diagram

 Main path (label = X/Z):
 A -1/0-> B -1/0-> C -0/0-> D -1/1-> B
 Other transitions:
 A -0/0-> A    B -0/0-> A
 C -1/0-> C    D -0/0-> A

Step 3: State assignment

Step 4: Excitation table

SR excitation: 0→0: S=0, R=X; 0→1: S=1, R=0; 1→0: S=0, R=1; 1→1: S=X, R=0.

Step 5: K-maps (rows $Q_1$, columns $Q_0X$)

Step 6: Equations

$$\begin{aligned} &S_1 = \overline{Q_1}Q_0X,\quad R_1 = Q_1Q_0 \\ &S_0 = Q_1\overline{Q_0}\overline{X} + \overline{Q_1}\overline{Q_0}X,\quad R_0 = \overline{Q_1}Q_0 + Q_0\overline{X} \\ &Z = Q_1Q_0X \end{aligned}$$

Step 7: Logic diagram

   +-----+       +-----+
S0>|S   Q|-Q0 S1>|S   Q|-Q1
   | FF0 |       | FF1 |
R0>|R    |    R1>|R    |
   +--^--+       +--^--+
      |             |
CLK---+-------------+
X = serial input, common to the gates
S1 = Q1'.Q0.X   R1 = Q1.Q0
S0 = Q1.Q0'.X' + Q1'.Q0'.X   R0 = Q1'.Q0 + Q0.X'
Z = Q1.Q0.X

The gates for each flip-flop input are built from the equations; the output gate gives Z directly (Mealy output).

Check with an input stream

Z = 1 appears exactly on the clock in which the last bit of 1101 arrives; overlapping sequences are also detected.

The detector watches the serial data stream X and makes Y = 1 when the last four bits received are 1, 0, 1, 1; otherwise Y = 0. Positive-edge triggered T flip-flops are used.

A Mealy machine is used (output depends on the present state and the present input), and overlapping sequences are detected. Since the sequence has 4 bits, 4 states are needed, so 2 T flip-flops ($Q_1Q_0$) are used, clocked on the positive edge. (A Moore machine would need 5 states.)

Step 1: States

Step 2: State diagram

 Main path (label = X/Y):
 A -1/0-> B -0/0-> C -1/0-> D -1/1-> B
 Other transitions:
 A -0/0-> A    B -1/0-> B
 C -0/0-> A    D -0/0-> C

Step 3: State assignment

Step 4: Excitation table

T excitation: T = 1 when the flip-flop must change, T = 0 when it must hold ($T = Q \oplus Q^+$).

Step 5: K-maps (rows $Q_1$, columns $Q_0X$)

Step 6: Equations

$$\begin{aligned} &T_1 = Q_1Q_0X + Q_1\overline{Q_0}\overline{X} + \overline{Q_1}Q_0\overline{X} \\ &T_0 = Q_0\overline{X} + \overline{Q_0}X \\ &Y = Q_1Q_0X \end{aligned}$$

Step 7: Logic diagram

   +-----+       +-----+
T0>|T   Q|-Q0 T1>|T   Q|-Q1
   | FF0 |       | FF1 |
   |     |       |     |
   +--^--+       +--^--+
      |             |
CLK---+-------------+
X = serial input, common to the gates
T1 = Q1.Q0.X + Q1.Q0'.X' + Q1'.Q0.X'
T0 = Q0.X' + Q0'.X
Y = Q1.Q0.X

The gates for each flip-flop input are built from the equations; the output gate gives Y directly (Mealy output).

Check with an input stream

Y = 1 appears exactly on the clock in which the last bit of 1011 arrives; overlapping sequences are also detected.

Note: $T_0 = Q_0 \oplus X$, so FF0 needs only one XOR gate.

The machine has one serial input X and one output Z; Z = 1 when the last four bits received are 1, 0, 1, 0. Since no flip-flop type is specified, JK flip-flops are used.

A Mealy machine is used (output depends on the present state and the present input), and overlapping sequences are detected. Since the sequence has 4 bits, 4 states are needed, so 2 JK flip-flops ($Q_1Q_0$) are used, clocked on the positive edge. (A Moore machine would need 5 states.)

Step 1: States

Step 2: State diagram

 Main path (label = X/Z):
 A -1/0-> B -0/0-> C -1/0-> D -0/1-> C
 Other transitions:
 A -0/0-> A    B -1/0-> B
 C -0/0-> A    D -1/0-> B

Step 3: State assignment

Step 4: Excitation table

JK excitation: 0→0: J=0, K=X; 0→1: J=1, K=X; 1→0: J=X, K=1; 1→1: J=X, K=0.

Step 5: K-maps (rows $Q_1$, columns $Q_0X$)

Step 6: Equations

$$\begin{aligned} &J_1 = Q_0\overline{X},\quad K_1 = Q_0X + \overline{Q_0}\overline{X} \\ &J_0 = X,\quad K_0 = \overline{X} \\ &Z = Q_1Q_0\overline{X} \end{aligned}$$

Step 7: Logic diagram

   +-----+       +-----+
J0>|J   Q|-Q0 J1>|J   Q|-Q1
   | FF0 |       | FF1 |
K0>|K    |    K1>|K    |
   +--^--+       +--^--+
      |             |
CLK---+-------------+
X = serial input, common to the gates
J1 = Q0.X'   K1 = Q0.X + Q0'.X'
J0 = X   K0 = X'
Z = Q1.Q0.X'

The gates for each flip-flop input are built from the equations; the output gate gives Z directly (Mealy output).

Check with an input stream

Z = 1 appears exactly on the clock in which the last bit of 1010 arrives; overlapping sequences are also detected.

Note: $K_1 = \overline{Q_0 \oplus X}$ (an XNOR gate), and FF0 simply follows the input ($J_0 = X$, $K_0 = \overline{X}$).

The machine watches the serial input X and makes Y = 1 when the last three bits received are 1, 0, 1.

A Mealy machine is used (output depends on the present state and the present input), and overlapping sequences are detected. Since the sequence has 3 bits, 3 states are needed, so 2 JK flip-flops ($Q_1Q_0$) are used, clocked on the positive edge. (A Moore machine would need 4 states.)

Step 1: States

Step 2: State diagram

 Main path (label = X/Y):
 A -1/0-> B -0/0-> C -1/1-> B
 Other transitions:
 A -0/0-> A    B -1/0-> B
 C -0/0-> A

Step 3: State assignment

Code 11 is unused and is treated as a don't care.

Step 4: Excitation table

JK excitation: 0→0: J=0, K=X; 0→1: J=1, K=X; 1→0: J=X, K=1; 1→1: J=X, K=0.

Step 5: K-maps (rows $Q_1$, columns $Q_0X$)

Step 6: Equations

$$\begin{aligned} &J_1 = Q_0\overline{X},\quad K_1 = 1 \\ &J_0 = X,\quad K_0 = \overline{X} \\ &Y = Q_1X \end{aligned}$$

Step 7: Logic diagram

   +-----+       +-----+
J0>|J   Q|-Q0 J1>|J   Q|-Q1
   | FF0 |       | FF1 |
K0>|K    |    K1>|K    |
   +--^--+       +--^--+
      |             |
CLK---+-------------+
X = serial input, common to the gates
J1 = Q0.X'   K1 = 1
J0 = X   K0 = X'
Y = Q1.X

The gates for each flip-flop input are built from the equations; the output gate gives Y directly (Mealy output).

Unused state 11: with the equations above, from 11 the machine goes to 00 when X = 0 and to 01 when X = 1, so it enters the valid states after one clock. Since Y can be 1 from state 11 for one clock, the flip-flops should be cleared to 00 at power-on (reset).

Check with an input stream

Y = 1 appears exactly on the clock in which the last bit of 101 arrives; overlapping sequences are also detected.

The machine has a single input x and a single output y; y = 1 when the last four bits received are 1, 1, 0, 1. Only T flip-flops are used.

A Mealy machine is used (output depends on the present state and the present input), and overlapping sequences are detected. Since the sequence has 4 bits, 4 states are needed, so 2 T flip-flops ($Q_1Q_0$) are used, clocked on the positive edge. (A Moore machine would need 5 states.)

Step 1: States

Step 2: State diagram

 Main path (label = x/y):
 A -1/0-> B -1/0-> C -0/0-> D -1/1-> B
 Other transitions:
 A -0/0-> A    B -0/0-> A
 C -1/0-> C    D -0/0-> A

Step 3: State assignment

Step 4: Excitation table

T excitation: T = 1 when the flip-flop must change, T = 0 when it must hold ($T = Q \oplus Q^+$).

Step 5: K-maps (rows $Q_1$, columns $Q_0x$)

Step 6: Equations

$$\begin{aligned} &T_1 = Q_1Q_0 + Q_0x \\ &T_0 = Q_1\overline{x} + \overline{Q_1}x + Q_0\overline{x} \\ &y = Q_1Q_0x \end{aligned}$$

Step 7: Logic diagram

   +-----+       +-----+
T0>|T   Q|-Q0 T1>|T   Q|-Q1
   | FF0 |       | FF1 |
   |     |       |     |
   +--^--+       +--^--+
      |             |
CLK---+-------------+
x = serial input, common to the gates
T1 = Q1.Q0 + Q0.x
T0 = Q1.x' + Q1'.x + Q0.x'
y = Q1.Q0.x

The gates for each flip-flop input are built from the equations; the output gate gives y directly (Mealy output).

Check with an input stream

y = 1 appears exactly on the clock in which the last bit of 1101 arrives; overlapping sequences are also detected.

The machine has one serial input X and one output Z; Z = 1 when the last four bits received are 1, 0, 1, 0. T flip-flops are used.

A Mealy machine is used (output depends on the present state and the present input), and overlapping sequences are detected. Since the sequence has 4 bits, 4 states are needed, so 2 T flip-flops ($Q_1Q_0$) are used, clocked on the positive edge. (A Moore machine would need 5 states.)

Step 1: States

Step 2: State diagram

 Main path (label = X/Z):
 A -1/0-> B -0/0-> C -1/0-> D -0/1-> C
 Other transitions:
 A -0/0-> A    B -1/0-> B
 C -0/0-> A    D -1/0-> B

Step 3: State assignment

Step 4: Excitation table

T excitation: T = 1 when the flip-flop must change, T = 0 when it must hold ($T = Q \oplus Q^+$).

Step 5: K-maps (rows $Q_1$, columns $Q_0X$)

Step 6: Equations

$$\begin{aligned} &T_1 = Q_1Q_0X + Q_1\overline{Q_0}\overline{X} + \overline{Q_1}Q_0\overline{X} \\ &T_0 = Q_0\overline{X} + \overline{Q_0}X \\ &Z = Q_1Q_0\overline{X} \end{aligned}$$

Step 7: Logic diagram

   +-----+       +-----+
T0>|T   Q|-Q0 T1>|T   Q|-Q1
   | FF0 |       | FF1 |
   |     |       |     |
   +--^--+       +--^--+
      |             |
CLK---+-------------+
X = serial input, common to the gates
T1 = Q1.Q0.X + Q1.Q0'.X' + Q1'.Q0.X'
T0 = Q0.X' + Q0'.X
Z = Q1.Q0.X'

The gates for each flip-flop input are built from the equations; the output gate gives Z directly (Mealy output).

Check with an input stream

Z = 1 appears exactly on the clock in which the last bit of 1010 arrives; overlapping sequences are also detected.

Note: $T_0 = Q_0 \oplus X$, so FF0 needs only one XOR gate.

The machine has a single input x and a single output z; z = 1 when the last three bits received are 0, 0, 1. Only JK flip-flops are used.

A Mealy machine is used (output depends on the present state and the present input), and overlapping sequences are detected. Since the sequence has 3 bits, 3 states are needed, so 2 JK flip-flops ($Q_1Q_0$) are used, clocked on the positive edge. (A Moore machine would need 4 states.)

Step 1: States

Step 2: State diagram

 Main path (label = x/z):
 A -0/0-> B -0/0-> C -1/1-> A
 Other transitions:
 A -1/0-> A    B -1/0-> A
 C -0/0-> C

Step 3: State assignment

Code 11 is unused and is treated as a don't care.

Step 4: Excitation table

JK excitation: 0→0: J=0, K=X; 0→1: J=1, K=X; 1→0: J=X, K=1; 1→1: J=X, K=0.

Step 5: K-maps (rows $Q_1$, columns $Q_0x$)

Step 6: Equations

$$\begin{aligned} &J_1 = Q_0\overline{x},\quad K_1 = x \\ &J_0 = \overline{Q_1}\overline{x},\quad K_0 = 1 \\ &z = Q_1x \end{aligned}$$

Step 7: Logic diagram

   +-----+       +-----+
J0>|J   Q|-Q0 J1>|J   Q|-Q1
   | FF0 |       | FF1 |
K0>|K    |    K1>|K    |
   +--^--+       +--^--+
      |             |
CLK---+-------------+
x = serial input, common to the gates
J1 = Q0.x'   K1 = x
J0 = Q1'.x'   K0 = 1
z = Q1.x

The gates for each flip-flop input are built from the equations; the output gate gives z directly (Mealy output).

Unused state 11: with the equations above, from 11 the machine goes to 10 when x = 0 and to 00 when x = 1, so it enters the valid states after one clock. Since z can be 1 from state 11 for one clock, the flip-flops should be cleared to 00 at power-on (reset).

Check with an input stream

z = 1 appears exactly on the clock in which the last bit of 001 arrives; overlapping sequences are also detected.

The machine has one input A and one output Y; Y = 1 when the last four bits received on A are 1, 0, 0, 1. Only D flip-flops are used.

A Mealy machine is used (output depends on the present state and the present input), and overlapping sequences are detected. Since the sequence has 4 bits, 4 states are needed, so 2 D flip-flops ($Q_1Q_0$) are used, clocked on the positive edge. (A Moore machine would need 5 states.)

Step 1: States

Step 2: State diagram

 Main path (label = A/Y):
 S0 -1/0-> S1 -0/0-> S2 -0/0-> S3 -1/1-> S1
 Other transitions:
 S0 -0/0-> S0    S1 -1/0-> S1
 S2 -1/0-> S1    S3 -0/0-> S0

Step 3: State assignment

Step 4: Excitation table

D excitation: $D = Q^+$ (D equals the next state).

Step 5: K-maps (rows $Q_1$, columns $Q_0A$)

Step 6: Equations

$$\begin{aligned} &D_1 = Q_1\overline{Q_0}\overline{A} + \overline{Q_1}Q_0\overline{A} \\ &D_0 = Q_1\overline{Q_0} + A \\ &Y = Q_1Q_0A \end{aligned}$$

Step 7: Logic diagram

   +-----+       +-----+
D0>|D   Q|-Q0 D1>|D   Q|-Q1
   | FF0 |       | FF1 |
   |     |       |     |
   +--^--+       +--^--+
      |             |
CLK---+-------------+
A = serial input, common to the gates
D1 = Q1.Q0'.A' + Q1'.Q0.A'
D0 = Q1.Q0' + A
Y = Q1.Q0.A

The gates for each flip-flop input are built from the equations; the output gate gives Y directly (Mealy output).

Check with an input stream

Y = 1 appears exactly on the clock in which the last bit of 1001 arrives; overlapping sequences are also detected.

Note: $D_1 = \overline{A}\,(Q_1 \oplus Q_0)$, so FF1 needs one XOR and one AND gate.

A Mealy machine is used (output depends on present state and input), so fewer states are needed. Overlapping sequences are allowed: after a detection the machine keeps the useful tail of the input. One input X and one output Z; Z = 1 in the clock period in which the last bit of 1001 arrives. Flip-flops: S-R.

States (what has been received so far):

• A: reset / no useful bits
• B: "1" received
• C: "10" received
• D: "100" received

State diagram (Mealy)

Arc label = input/output

 A --1/0--> B --0/0--> C --0/0--> D --1/1--> B

 A --0/0--> A  (self loop)
 B --1/0--> B  (self loop)
 C --1/0--> B
 D --0/0--> A

State table

State assignment

A = 00, B = 01, C = 10, D = 11 (flip-flop outputs $Q_1 Q_0$).

Excitation table of S-R flip-flop

Transition and excitation table

K-maps and simplified equations

S1          X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       1    0
Q1Q0=11       0    0
Q1Q0=10       x    0

R1          X=0  X=1
Q1Q0=00       x    x
Q1Q0=01       0    x
Q1Q0=11       1    1
Q1Q0=10       0    1

S0          X=0  X=1
Q1Q0=00       0    1
Q1Q0=01       0    x
Q1Q0=11       0    x
Q1Q0=10       1    1

R0          X=0  X=1
Q1Q0=00       x    0
Q1Q0=01       1    0
Q1Q0=11       1    0
Q1Q0=10       0    0

Z           X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       0    0
Q1Q0=11       0    1
Q1Q0=10       0    0

$$\begin{aligned} S_1 &= Q_1' Q_0 X' \\ R_1 &= Q_1 Q_0 + X \\ S_0 &= Q_1 Q_0' + X \\ R_0 &= Q_0 X' \\ Z &= Q_1 Q_0 X \end{aligned}$$

Logic diagram

           +-------------+     +----------+
 X  ------>| next-state  |---->| FF1, FF0 |--+--> Q1, Q0
    +----->| logic       |     |  (CLK)   |  |
    |      +-------------+     +----------+  |
    +-------------------<--------------------+
    |      +-------------+
    +----->| output      |----> Z
 X  ------>| logic       |
           +-------------+

Gates needed (two S-R flip-flops with a common clock; complements are taken from the $Q'$ outputs or NOT gates):

• $S_1$: a 3-input AND for $Q_1' Q_0 X'$.
• $R_1$: a 2-input AND for $Q_1 Q_0$; direct line $X$, combined in a 2-input OR gate.
• $S_0$: a 2-input AND for $Q_1 Q_0'$; direct line $X$, combined in a 2-input OR gate.
• $R_0$: a 2-input AND for $Q_0 X'$.
• $Z$: a 3-input AND for $Q_1 Q_0 X$.

Check: input X = 01001001 gives Z = 00001001; Z = 1 at the 5th and 8th bits, so overlapping 1001s are both detected.

A Mealy machine is used (output depends on present state and input), so fewer states are needed. Overlapping sequences are allowed: after a detection the machine keeps the useful tail of the input. One input X and one output Z; Z = 1 in the clock period in which the last bit of 1011 arrives. Flip-flops: J-K.

States (what has been received so far):

• A: reset / no useful bits
• B: "1" received
• C: "10" received
• D: "101" received

State diagram (Mealy)

Arc label = input/output

 A --1/0--> B --0/0--> C --1/0--> D --1/1--> B

 A --0/0--> A  (self loop)
 B --1/0--> B  (self loop)
 C --0/0--> A
 D --0/0--> C

State table

State assignment

A = 00, B = 01, C = 10, D = 11 (flip-flop outputs $Q_1 Q_0$).

Excitation table of J-K flip-flop

Transition and excitation table

K-maps and simplified equations

J1          X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       1    0
Q1Q0=11       x    x
Q1Q0=10       x    x

K1          X=0  X=1
Q1Q0=00       x    x
Q1Q0=01       x    x
Q1Q0=11       0    1
Q1Q0=10       1    0

J0          X=0  X=1
Q1Q0=00       0    1
Q1Q0=01       x    x
Q1Q0=11       x    x
Q1Q0=10       0    1

K0          X=0  X=1
Q1Q0=00       x    x
Q1Q0=01       1    0
Q1Q0=11       1    0
Q1Q0=10       x    x

Z           X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       0    0
Q1Q0=11       0    1
Q1Q0=10       0    0

$$\begin{aligned} J_1 &= Q_0 X' \\ K_1 &= Q_0 X + Q_0' X' \\ J_0 &= X \\ K_0 &= X' \\ Z &= Q_1 Q_0 X \end{aligned}$$

Logic diagram

           +-------------+     +----------+
 X  ------>| next-state  |---->| FF1, FF0 |--+--> Q1, Q0
    +----->| logic       |     |  (CLK)   |  |
    |      +-------------+     +----------+  |
    +-------------------<--------------------+
    |      +-------------+
    +----->| output      |----> Z
 X  ------>| logic       |
           +-------------+

Gates needed (two J-K flip-flops with a common clock; complements are taken from the $Q'$ outputs or NOT gates):

• $J_1$: a 2-input AND for $Q_0 X'$.
• $K_1$: a 2-input AND for $Q_0 X$; a 2-input AND for $Q_0' X'$, combined in a 2-input OR gate.
• $J_0$: direct line $X$.
• $K_0$: direct line $X'$.
• $Z$: a 3-input AND for $Q_1 Q_0 X$.

Check: input X = 1011011 gives Z = 0001001; Z = 1 at bits 4 and 7 (overlapping 1011011). From D, input 0 gives "1010" whose useful tail is "10", so D goes to C.

The machine stays in its own state when the input does not advance the sequence (A on 1, B on 0), and gives Z = 0 except when 011 is completed.

A Mealy machine is used (output depends on present state and input), so fewer states are needed. Overlapping sequences are allowed: after a detection the machine keeps the useful tail of the input. One input X and one output Z; Z = 1 in the clock period in which the last bit of 011 arrives. Flip-flops: S-R.

States (what has been received so far):

• A: reset, or last bit 1 not part of a sequence (stays in A on 1)
• B: "0" received (stays in B on further 0s)
• C: "01" received

State diagram (Mealy)

Arc label = input/output

 A --0/0--> B --1/0--> C --1/1--> A

 A --1/0--> A  (self loop)
 B --0/0--> B  (self loop)
 C --0/0--> B

State table

State assignment

A = 00, B = 01, C = 10 (flip-flop outputs $Q_1 Q_0$). The unused code 11 is taken as don't care (x) in all K-maps. The flip-flops are cleared to 00 at power-on (start state).

Excitation table of S-R flip-flop

Transition and excitation table

K-maps and simplified equations

S1          X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       0    1
Q1Q0=11       x    x
Q1Q0=10       0    0

R1          X=0  X=1
Q1Q0=00       x    x
Q1Q0=01       x    0
Q1Q0=11       x    x
Q1Q0=10       1    1

S0          X=0  X=1
Q1Q0=00       1    0
Q1Q0=01       x    0
Q1Q0=11       x    x
Q1Q0=10       1    0

R0          X=0  X=1
Q1Q0=00       0    x
Q1Q0=01       0    1
Q1Q0=11       x    x
Q1Q0=10       0    x

Z           X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       0    0
Q1Q0=11       x    x
Q1Q0=10       0    1

$$\begin{aligned} S_1 &= Q_0 X \\ R_1 &= Q_0' \\ S_0 &= X' \\ R_0 &= X \\ Z &= Q_1 X \end{aligned}$$

Logic diagram

           +-------------+     +----------+
 X  ------>| next-state  |---->| FF1, FF0 |--+--> Q1, Q0
    +----->| logic       |     |  (CLK)   |  |
    |      +-------------+     +----------+  |
    +-------------------<--------------------+
    |      +-------------+
    +----->| output      |----> Z
 X  ------>| logic       |
           +-------------+

Gates needed (two S-R flip-flops with a common clock; complements are taken from the $Q'$ outputs or NOT gates):

• $S_1$: a 2-input AND for $Q_0 X$.
• $R_1$: direct line $Q_0'$.
• $S_0$: direct line $X'$.
• $R_0$: direct line $X$.
• $Z$: a 2-input AND for $Q_1 X$.

Check: input X = 1011011 gives Z = 0001001; Z = 1 at bits 4 and 7.

The state diagram is a Mealy diagram with 3 states. To avoid confusion with the state names X, Y, Z, the input is called W and the output F. From the diagram, F = 1 only when the machine is in Z and W = 1, i.e. the machine detects three or more consecutive 1s. Flip-flops: S-R.

State diagram (given)

Arc label = input/output

 X --1/0--> Y --1/0--> Z --1/1--> Z

 X --0/0--> X  (self loop)
 Y --0/0--> X
 Z --0/0--> X

State table

State assignment

X = 00, Y = 01, Z = 10 (flip-flop outputs $Q_1 Q_0$). The unused code 11 is taken as don't care (x) in all K-maps. The flip-flops are cleared to 00 at power-on (start state). Checking the final equations, from 11 the machine goes to a valid state on the next clock (W=0 goes to X, W=1 goes to Z), so it is self-starting.

Excitation table of S-R flip-flop

Transition and excitation table

K-maps and simplified equations

S1          W=0  W=1
Q1Q0=00       0    0
Q1Q0=01       0    1
Q1Q0=11       x    x
Q1Q0=10       0    x

R1          W=0  W=1
Q1Q0=00       x    x
Q1Q0=01       x    0
Q1Q0=11       x    x
Q1Q0=10       1    0

S0          W=0  W=1
Q1Q0=00       0    1
Q1Q0=01       0    0
Q1Q0=11       x    x
Q1Q0=10       0    0

R0          W=0  W=1
Q1Q0=00       x    0
Q1Q0=01       1    1
Q1Q0=11       x    x
Q1Q0=10       x    x

F           W=0  W=1
Q1Q0=00       0    0
Q1Q0=01       0    0
Q1Q0=11       x    x
Q1Q0=10       0    1

$$\begin{aligned} S_1 &= Q_0 W \\ R_1 &= W' \\ S_0 &= Q_1' Q_0' W \\ R_0 &= Q_0 \\ F &= Q_1 W \end{aligned}$$

Logic diagram

           +-------------+     +----------+
 W  ------>| next-state  |---->| FF1, FF0 |--+--> Q1, Q0
    +----->| logic       |     |  (CLK)   |  |
    |      +-------------+     +----------+  |
    +-------------------<--------------------+
    |      +-------------+
    +----->| output      |----> F
 W  ------>| logic       |
           +-------------+

Gates needed (two S-R flip-flops with a common clock; complements are taken from the $Q'$ outputs or NOT gates):

• $S_1$: a 2-input AND for $Q_0 W$.
• $R_1$: direct line $W'$.
• $S_0$: a 3-input AND for $Q_1' Q_0' W$.
• $R_0$: direct line $Q_0$.
• $F$: a 2-input AND for $Q_1 W$.

Check: input W = 0111101 gives F = 0001100 — F = 1 at the 3rd and 4th consecutive 1, as the diagram requires (Z → Z on 1/1).

No flip-flop type is specified, so J-K flip-flops are used (output named Y in the question is written Z below; Y = Z).

A Mealy machine is used (output depends on present state and input), so fewer states are needed. Overlapping sequences are allowed: after a detection the machine keeps the useful tail of the input. One input X and one output Z; Z = 1 in the clock period in which the last bit of 100 arrives. Flip-flops: J-K.

States (what has been received so far):

• A: reset / no useful bits
• B: "1" received
• C: "10" received

State diagram (Mealy)

Arc label = input/output

 A --1/0--> B --0/0--> C --0/1--> A

 A --0/0--> A  (self loop)
 B --1/0--> B  (self loop)
 C --1/0--> B

State table

State assignment

A = 00, B = 01, C = 10 (flip-flop outputs $Q_1 Q_0$). The unused code 11 is taken as don't care (x) in all K-maps. The flip-flops are cleared to 00 at power-on (start state). Checking the final equations, from 11 the machine goes to a valid state on the next clock (X=0 goes to A, X=1 goes to B), so it is self-starting.

Excitation table of J-K flip-flop

Transition and excitation table

K-maps and simplified equations

J1          X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       1    0
Q1Q0=11       x    x
Q1Q0=10       x    x

K1          X=0  X=1
Q1Q0=00       x    x
Q1Q0=01       x    x
Q1Q0=11       x    x
Q1Q0=10       1    1

J0          X=0  X=1
Q1Q0=00       0    1
Q1Q0=01       x    x
Q1Q0=11       x    x
Q1Q0=10       0    1

K0          X=0  X=1
Q1Q0=00       x    x
Q1Q0=01       1    0
Q1Q0=11       x    x
Q1Q0=10       x    x

Z           X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       0    0
Q1Q0=11       x    x
Q1Q0=10       1    0

$$\begin{aligned} J_1 &= Q_0 X' \\ K_1 &= 1 \\ J_0 &= X \\ K_0 &= X' \\ Z &= Q_1 X' \end{aligned}$$

Logic diagram

           +-------------+     +----------+
 X  ------>| next-state  |---->| FF1, FF0 |--+--> Q1, Q0
    +----->| logic       |     |  (CLK)   |  |
    |      +-------------+     +----------+  |
    +-------------------<--------------------+
    |      +-------------+
    +----->| output      |----> Z
 X  ------>| logic       |
           +-------------+

Gates needed (two J-K flip-flops with a common clock; complements are taken from the $Q'$ outputs or NOT gates):

• $J_1$: a 2-input AND for $Q_0 X'$.
• $K_1$: tied to logic 1.
• $J_0$: direct line $X$.
• $K_0$: direct line $X'$.
• $Z$: a 2-input AND for $Q_1 X'$.

Check: input X = 1100100 gives Z = 0001001; Z = 1 at bits 4 and 7.

A Mealy machine is used (output depends on present state and input), so fewer states are needed. Overlapping sequences are allowed: after a detection the machine keeps the useful tail of the input. One input X and one output Z; Z = 1 in the clock period in which the last bit of 011 arrives. Flip-flops: J-K.

States (what has been received so far):

• A: reset, or last bits were 11 / 1
• B: "0" received
• C: "01" received

State diagram (Mealy)

Arc label = input/output

 A --0/0--> B --1/0--> C --1/1--> A

 A --1/0--> A  (self loop)
 B --0/0--> B  (self loop)
 C --0/0--> B

State table

State assignment

A = 00, B = 01, C = 10 (flip-flop outputs $Q_1 Q_0$). The unused code 11 is taken as don't care (x) in all K-maps. The flip-flops are cleared to 00 at power-on (start state). Checking the final equations, from 11 the machine goes to a valid state on the next clock (X=0 goes to B, X=1 goes to A), so it is self-starting.

Excitation table of J-K flip-flop

Transition and excitation table

K-maps and simplified equations

J1          X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       0    1
Q1Q0=11       x    x
Q1Q0=10       x    x

K1          X=0  X=1
Q1Q0=00       x    x
Q1Q0=01       x    x
Q1Q0=11       x    x
Q1Q0=10       1    1

J0          X=0  X=1
Q1Q0=00       1    0
Q1Q0=01       x    x
Q1Q0=11       x    x
Q1Q0=10       1    0

K0          X=0  X=1
Q1Q0=00       x    x
Q1Q0=01       0    1
Q1Q0=11       x    x
Q1Q0=10       x    x

Z           X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       0    0
Q1Q0=11       x    x
Q1Q0=10       0    1

$$\begin{aligned} J_1 &= Q_0 X \\ K_1 &= 1 \\ J_0 &= X' \\ K_0 &= X \\ Z &= Q_1 X \end{aligned}$$

Logic diagram

           +-------------+     +----------+
 X  ------>| next-state  |---->| FF1, FF0 |--+--> Q1, Q0
    +----->| logic       |     |  (CLK)   |  |
    |      +-------------+     +----------+  |
    +-------------------<--------------------+
    |      +-------------+
    +----->| output      |----> Z
 X  ------>| logic       |
           +-------------+

Gates needed (two J-K flip-flops with a common clock; complements are taken from the $Q'$ outputs or NOT gates):

• $J_1$: a 2-input AND for $Q_0 X$.
• $K_1$: tied to logic 1.
• $J_0$: direct line $X'$.
• $K_0$: direct line $X$.
• $Z$: a 2-input AND for $Q_1 X$.

Check: input X = 0011011 gives Z = 0001001; Z = 1 at bits 4 and 7 ("high output" when 011 ends).

A state diagram is a graph that shows the behaviour of a sequential circuit: each state is a circle, and each arrow shows the move to the next state on a clock pulse, labelled input/output (Mealy) or with the output written inside the circle (Moore).

A state table gives the same information in tabular form: for every present state and input, it lists the next state and the output.

Example: a Mealy machine that gives Z = 1 when two consecutive 1s arrive (states A = no 1, B = one 1).

 Arc label = X/Z

 A --1/0--> B --1/1--> B  (self loop)
 A --0/0--> A  (self loop)
 B --0/0--> A

No flip-flop type is specified, so D flip-flops are used (simplest: D = next state).

A Mealy machine is used (output depends on present state and input), so fewer states are needed. Overlapping sequences are allowed: after a detection the machine keeps the useful tail of the input. One input X and one output Z; Z = 1 in the clock period in which the last bit of 110 arrives. Flip-flops: D.

States (what has been received so far):

• A: reset / last bit 0
• B: "1" received
• C: "11" received (stays in C on more 1s)

State diagram (Mealy)

Arc label = input/output

 A --1/0--> B --1/0--> C --0/1--> A

 A --0/0--> A  (self loop)
 B --0/0--> A
 C --1/0--> C  (self loop)

State table

State assignment

A = 00, B = 01, C = 10 (flip-flop outputs $Q_1 Q_0$). The unused code 11 is taken as don't care (x) in all K-maps. The flip-flops are cleared to 00 at power-on (start state). Checking the final equations, from 11 the machine goes to a valid state on the next clock (X=0 goes to A, X=1 goes to C), so it is self-starting.

Excitation table of D flip-flop

Transition and excitation table

K-maps and simplified equations

D1          X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       0    1
Q1Q0=11       x    x
Q1Q0=10       0    1

D0          X=0  X=1
Q1Q0=00       0    1
Q1Q0=01       0    0
Q1Q0=11       x    x
Q1Q0=10       0    0

Z           X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       0    0
Q1Q0=11       x    x
Q1Q0=10       1    0

$$\begin{aligned} D_1 &= Q_0 X + Q_1 X \\ D_0 &= Q_1' Q_0' X \\ Z &= Q_1 X' \end{aligned}$$

Logic diagram

           +-------------+     +----------+
 X  ------>| next-state  |---->| FF1, FF0 |--+--> Q1, Q0
    +----->| logic       |     |  (CLK)   |  |
    |      +-------------+     +----------+  |
    +-------------------<--------------------+
    |      +-------------+
    +----->| output      |----> Z
 X  ------>| logic       |
           +-------------+

Gates needed (two D flip-flops with a common clock; complements are taken from the $Q'$ outputs or NOT gates):

• $D_1$: a 2-input AND for $Q_0 X$; a 2-input AND for $Q_1 X$, combined in a 2-input OR gate.
• $D_0$: a 3-input AND for $Q_1' Q_0' X$.
• $Z$: a 2-input AND for $Q_1 X'$.

Check: input X = 0110110 gives Z = 0001001; Z = 1 at bits 4 and 7.

No flip-flop type is specified, so J-K flip-flops are used. Output Y of the question is written Z (Y = Z). With overlapping, a run of four 0s gives Y = 1 on the 3rd and 4th zero.

A Mealy machine is used (output depends on present state and input), so fewer states are needed. Overlapping sequences are allowed: after a detection the machine keeps the useful tail of the input. One input X and one output Z; Z = 1 in the clock period in which the last bit of 000 arrives. Flip-flops: J-K.

States (what has been received so far):

• A: reset / last bit 1
• B: one 0 received
• C: two or more consecutive 0s received

State diagram (Mealy)

Arc label = input/output

 A --0/0--> B --0/0--> C --0/1--> C

 A --1/0--> A  (self loop)
 B --1/0--> A
 C --1/0--> A

State table

State assignment

A = 00, B = 01, C = 10 (flip-flop outputs $Q_1 Q_0$). The unused code 11 is taken as don't care (x) in all K-maps. The flip-flops are cleared to 00 at power-on (start state). Checking the final equations, from 11 the machine goes to a valid state on the next clock (X=0 goes to C, X=1 goes to A), so it is self-starting.

Excitation table of J-K flip-flop

Transition and excitation table

K-maps and simplified equations

J1          X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       1    0
Q1Q0=11       x    x
Q1Q0=10       x    x

K1          X=0  X=1
Q1Q0=00       x    x
Q1Q0=01       x    x
Q1Q0=11       x    x
Q1Q0=10       0    1

J0          X=0  X=1
Q1Q0=00       1    0
Q1Q0=01       x    x
Q1Q0=11       x    x
Q1Q0=10       0    0

K0          X=0  X=1
Q1Q0=00       x    x
Q1Q0=01       1    1
Q1Q0=11       x    x
Q1Q0=10       x    x

Z           X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       0    0
Q1Q0=11       x    x
Q1Q0=10       1    0

$$\begin{aligned} J_1 &= Q_0 X' \\ K_1 &= X \\ J_0 &= Q_1' X' \\ K_0 &= 1 \\ Z &= Q_1 X' \end{aligned}$$

Logic diagram

           +-------------+     +----------+
 X  ------>| next-state  |---->| FF1, FF0 |--+--> Q1, Q0
    +----->| logic       |     |  (CLK)   |  |
    |      +-------------+     +----------+  |
    +-------------------<--------------------+
    |      +-------------+
    +----->| output      |----> Z
 X  ------>| logic       |
           +-------------+

Gates needed (two J-K flip-flops with a common clock; complements are taken from the $Q'$ outputs or NOT gates):

• $J_1$: a 2-input AND for $Q_0 X'$.
• $K_1$: direct line $X$.
• $J_0$: a 2-input AND for $Q_1' X'$.
• $K_0$: tied to logic 1.
• $Z$: a 2-input AND for $Q_1 X'$.

Check: input X = 1000010 gives Z = 0001100; Z = 1 at the 4th and 5th bits (third and fourth consecutive 0).

"Starting from the MSB" means the bits arrive serially in the order 1, 1, 0 (MSB first).

A Mealy machine is used (output depends on present state and input), so fewer states are needed. Overlapping sequences are allowed: after a detection the machine keeps the useful tail of the input. One input X and one output Z; Z = 1 in the clock period in which the last bit of 110 arrives. Flip-flops: S-R.

States (what has been received so far):

• A: reset / last bit 0
• B: "1" (first bit, MSB) received
• C: "11" received

State diagram (Mealy)

Arc label = input/output

 A --1/0--> B --1/0--> C --0/1--> A

 A --0/0--> A  (self loop)
 B --0/0--> A
 C --1/0--> C  (self loop)

State table

State assignment

A = 00, B = 01, C = 10 (flip-flop outputs $Q_1 Q_0$). The unused code 11 is taken as don't care (x) in all K-maps. The flip-flops are cleared to 00 at power-on (start state). Checking the final equations, from 11 the machine goes to a valid state on the next clock (X=0 goes to A, X=1 goes to C), so it is self-starting.

Excitation table of S-R flip-flop

Transition and excitation table

K-maps and simplified equations

S1          X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       0    1
Q1Q0=11       x    x
Q1Q0=10       0    x

R1          X=0  X=1
Q1Q0=00       x    x
Q1Q0=01       x    0
Q1Q0=11       x    x
Q1Q0=10       1    0

S0          X=0  X=1
Q1Q0=00       0    1
Q1Q0=01       0    0
Q1Q0=11       x    x
Q1Q0=10       0    0

R0          X=0  X=1
Q1Q0=00       x    0
Q1Q0=01       1    1
Q1Q0=11       x    x
Q1Q0=10       x    x

Z           X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       0    0
Q1Q0=11       x    x
Q1Q0=10       1    0

$$\begin{aligned} S_1 &= Q_0 X \\ R_1 &= X' \\ S_0 &= Q_1' Q_0' X \\ R_0 &= Q_0 \\ Z &= Q_1 X' \end{aligned}$$

Logic diagram

           +-------------+     +----------+
 X  ------>| next-state  |---->| FF1, FF0 |--+--> Q1, Q0
    +----->| logic       |     |  (CLK)   |  |
    |      +-------------+     +----------+  |
    +-------------------<--------------------+
    |      +-------------+
    +----->| output      |----> Z
 X  ------>| logic       |
           +-------------+

Gates needed (two S-R flip-flops with a common clock; complements are taken from the $Q'$ outputs or NOT gates):

• $S_1$: a 2-input AND for $Q_0 X$.
• $R_1$: direct line $X'$.
• $S_0$: a 3-input AND for $Q_1' Q_0' X$.
• $R_0$: direct line $Q_0$.
• $Z$: a 2-input AND for $Q_1 X'$.

Check: input X = 0110110 gives Z = 0001001; Z = 1 at bits 4 and 7.

An asynchronous sequential circuit has no clock: its state (held in feedback loops through gate delays) changes as soon as an input changes. This makes it fast, but the design has several problems that clocked circuits avoid.

1. Races

A race happens when two or more state variables must change in one transition. Due to unequal delays they do not change together, so the circuit passes through an intermediate state.

• Non-critical race: the circuit still reaches the correct final state whatever order the variables change in.
• Critical race: the final stable state depends on which variable changes first, so the circuit may settle in a wrong state.

Example: state $y_1 y_2$ must go from 00 to 11. If $y_1$ changes first the circuit passes 10; if $y_2$ first, it passes 01. If, for the present input, 01 is a stable state, the circuit stops at 01 instead of 11 — a critical race.

  00 ---> 11   intended
  00 ---> 10 ---> 11   (y1 first, OK)
  00 ---> 01 (stable) stuck  (y2 first, error)

Remedy: choose a race-free state assignment (adjacent codes differing in one bit), add extra states, or use a one-hot code.

2. Cycles

The circuit may go through a sequence of unstable states before reaching a stable one. If no stable state exists in that column, it keeps oscillating (an unending cycle) between states.

3. Hazards

Unequal gate delays give momentary wrong outputs (glitches):

• Static-1 hazard: output should stay 1 but drops to 0 briefly, e.g. $F = AB + A'C$ when A changes with B = C = 1. Fixed by adding the consensus term $BC$.
• Static-0 / dynamic hazards are similar for 0 and for changing outputs.
• Essential hazard: caused by an input change reaching different parts of the circuit at different times; removed by adding delay in the feedback.

Because feedback carries these glitches, a hazard can push the circuit into a wrong stable state.

4. Other restrictions

• Fundamental mode: only one input may change at a time, and only after the circuit is stable.
• Analysis and design are harder (flow table, merging of rows, state assignment), and the circuit is sensitive to temperature and delay variations.

A Mealy machine is used (output depends on present state and input), so fewer states are needed. Overlapping sequences are allowed: after a detection the machine keeps the useful tail of the input. One input X and one output Z; Z = 1 in the clock period in which the last bit of 110 arrives. Flip-flops: J-K.

States (what has been received so far):

• A: reset / last bit 0
• B: "1" received
• C: "11" received (stays in C on more 1s)

State diagram (Mealy)

Arc label = input/output

 A --1/0--> B --1/0--> C --0/1--> A

 A --0/0--> A  (self loop)
 B --0/0--> A
 C --1/0--> C  (self loop)

State table

State assignment

A = 00, B = 01, C = 10 (flip-flop outputs $Q_1 Q_0$). The unused code 11 is taken as don't care (x) in all K-maps. The flip-flops are cleared to 00 at power-on (start state). Checking the final equations, from 11 the machine goes to a valid state on the next clock (X=0 goes to A, X=1 goes to C), so it is self-starting.

Excitation table of J-K flip-flop

Transition and excitation table

K-maps and simplified equations

J1          X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       0    1
Q1Q0=11       x    x
Q1Q0=10       x    x

K1          X=0  X=1
Q1Q0=00       x    x
Q1Q0=01       x    x
Q1Q0=11       x    x
Q1Q0=10       1    0

J0          X=0  X=1
Q1Q0=00       0    1
Q1Q0=01       x    x
Q1Q0=11       x    x
Q1Q0=10       0    0

K0          X=0  X=1
Q1Q0=00       x    x
Q1Q0=01       1    1
Q1Q0=11       x    x
Q1Q0=10       x    x

Z           X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       0    0
Q1Q0=11       x    x
Q1Q0=10       1    0

$$\begin{aligned} J_1 &= Q_0 X \\ K_1 &= X' \\ J_0 &= Q_1' X \\ K_0 &= 1 \\ Z &= Q_1 X' \end{aligned}$$

Logic diagram

           +-------------+     +----------+
 X  ------>| next-state  |---->| FF1, FF0 |--+--> Q1, Q0
    +----->| logic       |     |  (CLK)   |  |
    |      +-------------+     +----------+  |
    +-------------------<--------------------+
    |      +-------------+
    +----->| output      |----> Z
 X  ------>| logic       |
           +-------------+

Gates needed (two J-K flip-flops with a common clock; complements are taken from the $Q'$ outputs or NOT gates):

• $J_1$: a 2-input AND for $Q_0 X$.
• $K_1$: direct line $X'$.
• $J_0$: a 2-input AND for $Q_1' X$.
• $K_0$: tied to logic 1.
• $Z$: a 2-input AND for $Q_1 X'$.

Check: input X = 1110110 gives Z = 0001001; Z = 1 at bits 4 and 7.