Chapter 4: Finite State Machine – Introduction to Automata Theory, Formal Languages and Computation

4

Finite State Machine

Introduction

Chapter 3 already discusses the Mealy and Moore machines. These machines fall in the category of automata with output. Finite state machine, in short FSM, is a machine with a finite number of states. As all finite automata contain finite number of states, they are FSMs also. In this chapter, we shall discuss elaborately the different features of an FSM, some application such as sequence detector, incompletely specified machine, where some states and/or some outputs are not mentioned, definite machine, finite machine, information lossless machine, minimization of machines, etc.

4.1  Sequence Detector

The sequence detector detects and counts a particular sequence from a long input. Let us assume that, in a circuit, a long input of ‘0’ and ‘1’ is fed. Let us also assume that, from there, it needs to count the occurring of a particular sequence where overlapping sequences are also counted. The circuit generates ‘1’ if the particular output pattern is generated; otherwise, ‘0’ is generated.

The sequence detector can be designed either in a Mealy or Moore machine format.

The following examples describe the design of a sequence detector elaborately.

Example 4.1

Design a two-input two-output sequence detector which generates an output ‘1’ every time the sequence 1001 is detected. And for all other cases, output ‘0’ is generated. Overlapping sequences are also counted.

Solution: Before designing this circuit, some clarification regarding overlapping sequence is needed.

Let the input string be 1001001.

We have to design the circuit in such a way that it will take one input at a time. The input can be either ‘0’ or ‘1’ (two types of input). The output will also be of two types, either ‘0’ or ‘1’. The circuit can store (memorize) the input string up to four clock pulses from ti−3 to ti.

If the input string is placed according to clock pulses, the output will become

Fig. 4.1 Overlapping Sequence

The first input at t1 is 1, and as there is no input from ti-3 to ti, the input sequence does not equal 1001. So, the output will be 0. The same cases occur for the inputs up to t3.

But at time t4, the input from ti-3 to ti becomes 1001, and so the output ‘1’ is produced at time t4. At time t5 and t6, the input string from ti-3 to ti are 0010 and 0100, respectively. So, the output ‘0’ is produced. But at t7 clock pulse, the input string is 1001, and so the output ‘1’ is produced. As the ‘1’ at t4 is overlapped from t1 to t4 and from t4 to t7, this is called overlapping condition as shown in Fig. 4.1.

For this case, we have to first draw the state diagram given in Fig. 4.2.

Fig. 4.2 State Diagram of the Sequence Detector

In state S1, the input may be either ‘0’ or ‘1’. If the input is given ‘0’, there is no chance to get 1001. The machine has to wait for the next input. So, ‘0’ becomes a loop on S1 with output ‘0’.

If the input is ‘1’, there is a chance to get 1001 by considering that input, and so by getting input ‘1’ the machine moves to S2 producing output ‘0’.

In S2, again the input may be either ‘0’ or ‘1’. If it is ‘1’, the input becomes 11. There is no chance to get 1001 by taking the previous inputs from ti-1 to ti. But there is a chance to get 1001 by considering the given input ‘1’ at ti. So, it will be in state S2. (If it goes to S1, then there will be a loss of clock pulse, which means again from S1 by taking input ‘1’, it has to come to S2, i.e., one extra input, which means one clock pulse is needed, and for this the output will not be in right pattern.) If the input is ‘0’, the input becomes 10, by considering the previous input. As there is a chance to get 1001, it will move to S3.

In S3, if it gets input ‘0’, the input becomes 100 by considering the previous input. As it has a chance to get 1001, it shifts to S4. But if it gets ‘0’, it has no chance to get 1001 considering the previous input, but there is a chance to get 1001 by considering the given input ‘1’. So, it will shift to S2 as we know by getting ‘1’ in S1 the machine comes to S2.

In S4, if it gets ‘0’, the input will become 1000, but it does not match with 1001. So it has to start from the beginning, i.e., S1. Getting ‘1’, the string becomes the desired 1001. The overlapping part is the last ‘1’ as given in Fig. 4.1. From the last ‘1’ of 1001, if it gets 001 only, it will give an output ‘1’. So, it will go to S2.

State Table: From the previous state diagram, a state graph can be easily constructed.

Present State
Next State, O/P
X = 0
= 1
S1
S1, 0
S2, 0
S2
S3, 0
S2, 0
S3
S4, 0
S2, 0
S4
S1, 0
S2, 1

State Assignment: For making a digital circuit, the states must be assigned to some binary numbers. This is called state assignment. As the number of states is 4, only two-digit is sufficient to represent the four states (22 = 4).

Let S1 be assigned to 00, S2 be assigned to 01, S3 be assigned to 11, S4 be assigned to 10.

After doing this state assignment, the state table becomes

From this state assignment table, the digital function can easily be derived.

Y1 and Y2 are the next states, which are the memory elements. These will be feedbacked to the input as states y1 and y2 with some delay by D flip flop.

The circuit diagram for this sequence detector is given in Fig. 4.3.

Fig. 4.3 Digital Circuit for the Sequence Detector

Example 4.2

Design a two-input two-output sequence detector which generates an output ‘1’ every time the sequence 1010 is detected. And for all other cases, output ‘0’ is generated. Overlapping sequences are also counted.

Solution: The input string 1010100 is placed according to the clock pulses, and it looks like the following.

Fig. 4.4 Overlapping Sequence

And the output becomes as given earlier. Overlapping portion is 10, as shown in Fig. 4.4.

The state diagram is given in Fig. 4.5.

Fig. 4.5 State Diagram

State Table: From the previous state diagram, a state table as follows can easily be constructed.

Present State
Next State, O/P
X = 0
= 1
S1
S1, 0
S2, 0
S2
S3, 0
S2, 0
S3
S1, 0
S4, 0
S4
S3, 0
S2, 0

State Assignments: For making a digital circuit, the states must be assigned to some binary numbers to make a digital circuit. This is called state assignment. As the number of states is 4, two-digit is sufficient to represent the four states (22 = 4).

Let S1 be assigned to 00, S2 be assigned to 01, S3 be assigned to 11, S4 be assigned to 10.

After doing this state assignment, the state table becomes

From this state assignment table, the digital function can easily be derived as follows.

Y1 and Y2 are the next states, which are the memory elements. These will be feedbacked to the input as states y1 and y2 with some delay by D flip flop. The circuit diagram is shown in Fig. 4.6.

Fig. 4.6 Digital Circuit Diagram

4.2  Binary Counter

The binary counter counts in binary.

Example 4.3

Design a Modulo 3 binary counter.

Solution: A Modulo 3 binary counter can count up to 3. The binary representation of 3 is 11. It can count 00, 01, 10, and 11. There will be an external input x, which will act as a control variable and determine when the count should proceed. After counting 3, if it has to proceed, then it will come back to 00 again.

The state diagram for a Mod 3 binary counter is given in Fig. 4.7.

Fig. 4.7 State Diagram of a Mod 3 Binary Counter

The state table for Mod 3 binary counter is

Present State
Next State, O/P
X = 0
X = 1
S1
S1, 0
S2, 0
S2
S2, 0
S3, 0
S3
S3, 0
S4, 0
S4
S4, 0
S1, 1

There are four states in the machine. Two bits are sufficient to assign four states into the binary number.

Let us assign S1 to 00, S2 to 01, S3 to 10, and S4 to 11.

After doing this state assignment, the state table becomes

4.2.1  Designing Using Flip Flop (T Flip Flop and SR Flip Flop)

The excitation table for T flip flop is given in the following:

Circuit From
Changed To
T
0
0
0
0
1
1
1
0
1
1
1
0

In state assignment, 00 is changed to 00 for input 0. Here, y1 is changed from 0 to 0, and so T1 will be 0. y2 is changed from 0 to 1, and so T1 will be 0. 00 is changed to 01 for input 1. Here, y1 is changed from 0 to 1, and so T1 will be 1. y2 is changed from 0 to 0, and so T1 will be 0. By this process, the excitation table of the counter using T flip flop is given in the following table.

Present State (y2y1)
T2T1
X = 0
X = 1
00
00
01
01
00
11
10
00
01
11
00
11

The circuit diagram for this is presented in Fig. 4.8.

Fig. 4.8 Circuit Diagram Using T Flip Flop

The excitation table for SR flip flop is denoted in the following table.

In state assignment, 00 is changed to 00 for input 0. Here, y1 is changed from 0 to 0, and so R1 will be don’t care and S1 will be 0. y2 is changed from 0 to 0, and so R2 will be don’t care and S2 will be 0. In the state assignment table, 00 is changed to 01 for input 1. Here, y1 is changed from 0 to 1, and so R1 will be 0 and S1 will be 1. y2 is changed from 0 to 0, and so R2 will be don’t care and S2 will be 0. By this process, the excitation table of the counter using SR flip flop is given as follows.

The circuit diagram for this is presented in Fig. 4.9.

Fig. 4.9 Circuit Diagram Using SR Flip Flop

Example 4.4

Design a Modulo 8 binary counter

Solution: A Modulo 8 binary counter can count up to 8 from 000 to 111. There will be an external input x, which will act as a control variable and determine when the count should proceed. After counting 8, if it has to proceed, then it will come back to 000 again.

The state diagram for a Mod 8 binary counter is given in Fig. 4.10.

Fig. 4.10 A Modulo 8 Binary Counter

The state table for a Mod 8 binary counter is

Present State
Next State, O/P
X = 0
X = 1
S0
S0, 0
S1, 0
S1
S1, 0
S2, 0
S2
S2, 0
S3, 0
S3
S3, 0
S4, 0
S4
S4, 0
S5, 0
S5
S5, 0
S6, 0
S6
S6, 0
S7, 0
S7
S7, 0
S0, 1

State Assignment: There are eight states in the machine. Three bits are sufficient to assign eight states into binary number (23 = 8).

Let us assign S1 to 000, S2 to 001, S3 to 010, S4 to 011, S5 to 100, S6 to 101, S7 to 101, and S8 to 111.

The excitation table of the counter using T flip flop is as follows.

Present State (y3y2y1)
T3T2T1
X = 0
X = 1
000
000
001
001
000
011
010
000
001
011
000
111
100
000
001
101
000
011
101
000
001
111
000
111
T1 = X    T2 = Xy1   T3 = Xy1y2    z = Xy1y2y3

 

The circuit diagram for this is shown in Fig. 4.11.

Fig. 4.11 Circuit Diagram Using T Flip Flop

The excitation table of the counter using SR flip flop is given in the following table.

The circuit diagram for this is presented in Fig. 4.12.

Fig. 4.12 Circuit Diagram Using SR Flip Flop

4.3  Finite State Machine

An FSM can be defined as a type of machine whose past histories can affect its future behaviour in a finite number of ways.

Need some clarification . . . . Take the example of a binary full adder. Its output depends on the present input and the carry generated from the previous input.

It may have a large number of previous input histories, but they can be divided into two types: (i) input combination that produces carry and (ii) input combination that produces no carry.

This means that the past histories can affect the future behaviour in a finite number of ways (here 2).

4.3.1  Capabilities and Limitations of Finite-State Machine

Let us assume that an FSM has n states. Let a long sequence of input be given to the machine. The machine will progress starting from its beginning state to the next states according to the state transitions as described in Fig. 4.13. But after some time, the input string may be longer than ‘n’, the number of states. But as there are only ‘n’ states in the machine, it must come to a state it was previously been in, and from this phase if the input remains the same the machine will function in a periodically repeating fashion. From here, a conclusion that ‘for an ‘n’ state machine, the output will become periodic after a number of clock pulses less than equal to ‘n’ can be drawn.

The states are memory elements. As for an FSM, the number of states is finite, and so a finite number of memory elements are required to design a finite state machine.

Fig. 4.13

4.3.1.1  Limitations

No FSM Can be Produced for an Infinite Sequence: Let us design an FSM which receives a long sequence of 1. The machine will produce an output 1, when the input string length will be equal to [p(p + 1)]/2, where p = 1, 2, 3, . . . . . . . , and 0 for all other cases.

For this type of machine, the input–output form will be

Here, the output does not become eventually periodic after a certain number of clock pulses. So, from this type of sequence, no FSM can be produced.

No FSM Can Multiply Two Arbitrary Large Binary Numbers: Let us multiply two binary numbers that are given input serially to an FSM for multiplication. The inputs are given to the machine with the least significant bit (LSB) first and then the other bits. Suppose we want to multiply 2m × 2m, where m > n (‘n’ is the number of states of the machine). The result will be 22m.

2m is represented by one 1 followed by m number of ‘0’s (like 23 = 1000). So, the inputs are given to the machine from t1 to tm + 1 time. Throughout the time, the machine produces ‘0’. At tm + 2 times, the input stops and the machine produces the output 0 followed by 1 from tm + 2 to t2m time.

In the time period tm + 1 to t2m, no input is given to the machine, but the machine produces outputs. As m > n, according to the definition of FSM, the output must be periodic and the period must be < m.

As we are not getting any repeating output sequence, the binary multiplication of two arbitrary, large binary numbers is not possible to be designed by using FSM.

FSM Cannot Check Whether a String is Palindrome or Not: It is not able to find where a string ends and its reverse string starts or the middle of the string.

4.4  State Equivalence and Minimization of Machine

In chapter 3, we have already learnt how to minimize finite automata. In this section, we shall learn how to minimize an FSM.

The state of a machine means memory elements. A machine with more states means more memory elements are required. For an N state machine, log2N state variables are needed for state assignment. More state variables means designing the machine becomes more complex. Machine minimization reduces the number of states, which consequently reduces the complexity of designing the machine.

Two states Si and Sj of machine M are said to be equivalent if they produce the same output sequences for an input string applied to the machine M, considering Si and Sj as initial states.

Two states Si and Sj of machine M are said to be distinguishable if there exists a minimum length input sequence which when applied to the machine M, considering Si and Sj as the initial states, produce different output sequence. (The input string is always applied on initial state.)

The sequence that distinguishes those two states is called the distinguishing sequence for the pair Si and Sj.

If two states Si and Sj are distinguished for the input string of length ‘k’, then Si and Sj are called k-distinguishable. ‘k’ is the minimum number of the length of the string for which the states produce different output. If two states are k-distinguishable, then they are (k − 1) equivalent for k = k to 1.

From the following state table, the concept will be clear.

Present State
Next State, z
X = 0
X = 1
A
E, 0
C, 0
B
F, 0
C, 1
C
E, 0
A, 0
D
F, 0
A, 1
E
A, 0
D, 0
F
D, 0
E, 1

Take the previous example.

A and C give the same output (here 0) for the input string of length 1 (either 0 or 1). So, A and C are 1-equivalent.

A and B give different outputs for input string of length 1. (For input string length 0, i.e., for no input—the outputs are same; but for 1, they produce different outputs.) So, A and B are 1-distinguishable.

Let us check for string length 2. String length 2 means that it gives four types of combinations 00, 01, 11, and 10.

A and E are 2-distinguishable, as they produce different outputs for 11. The distinguishing sequence for A and E is 11.

The equivalent partition of a machine M can be defined as a set of maximum number subsets of states where states which reside in same subset are equivalent for any input given to the states. The states which reside in different subsets are distinguishable for some input.

Definition: The equivalent partition of an FSM is unique.

Proof: Suppose for a machine M there exist two equivalent partitions P1 and P2, where P1 ≠ P2. As P1 ≠ P2, there must exist at least two states Si and Sj, which are in the same block of one partition (say, P1) and in different blocks in other partition (say, P2). As they are in different blocks in P2, there must exist an input sequence which distinguishes Si and Sj. So, they cannot be in the same block of P1. Therefore, our assumption is wrong. For a single machine, there cannot exist two equivalent partitions.

So, from here we can conclude that equivalent partition is unique, i.e., P1 ≡ P2.

The following are some examples of finding an equivalent partition of some machines and minimizing those machines.

Example 4.5

Find the equivalent partitions and minimize the following finite state machine.

Solution:

Present State
Next State, z
X = 0
X = 1
A
E, 0
C, 0
B
F, 0
C, 1
C
E, 0
A, 0
D
F, 0
A, 1
E
A, 0
D, 0
F
D, 0
E, 1

For string length 0 (i.e., for no input), there is no output. So, all the states are equivalent.

 

P0 = (ABCDEF)

 

Consider for string length 1 (i.e., two inputs 0 or 1). For 0, for all states, the output is 0. For 1, we get different outputs for (ACE) and (BDF). A and B are 1-distinguishable. A and C are 1-equivalent.

So,

 

P1 = ((ACE) (BDF))

 

Consider for string length 2 (i.e., four types of input 00, 01, 11, and 10).

For A and C, the outputs are the same for 00, 01, 11, and 10. But E has a different output for 11. For B, D, F, the outputs are the same for all inputs.

 

P2 = ((AC)(E)(BDF))

 

Consider for string length 3 (i.e., eight types of input combinations). So, it will be difficult to find the output sequences and the equivalent partitions, as the length of input string increases.

It will be easier to check for the next states.

We know

 

P1 = ((ACE) (BDF))

 

Let us rename (ACE) as set S1 and (BDF) as set S2.

For ACE with input 0, the next states are (EEA). Both A and E belong to set S1. For input 1, the next states are (CAD). Here, A and C belong to set S1, but D belongs to set S2. So, the set (ACE) will be divided as (AC) and (E) for input string length 2.

For (BDF) with input 0, the next states are (FFD). Both F and D belong to the same set S2. For input 1, the next states are (CAE). All of these belong to same set S1. So, (BDF) cannot be divided for input string length 2.

The partition of states become

 

P2 = (AC)(E)(BDF) (the same result is obtained with considering output).

 

Let us check for input string length 3.

For (AC) with input 0, the next states are (EE). Both the next states belong to a single set. For input 1, the next states are (AC). Both the next states belong to a single set. So, (AC) cannot be divided for input string length 3.

(E) is a set of single state. So, (E) cannot be divided.

For (BDF) with input 0, the next states are (FFD). All of them belong to a single set. With input 1, the next states are (CAE). C and A belong to one set in P2 and E belongs to another set in P2. So, (BDF) will be divided as (BD) and (F) for input string length 3.

The partition of states become

 

P3 = (AC)(E)(BD)(F)

 

Let us check for input string length 4.

For (AC) with input 0, the next states are (EE), belonging to a single set. For input 1, the next states are (AC), belonging to a single set. So, (AC) cannot be divided for input string length 4.

(E) is a set of single state. So, (E) cannot be divided.

For (BD) with input 0 and 1, the next states are (FF) and (AC), respectively. (FF) belong to a single set and (AC) also belong to a single set. So, (BD) cannot be divided. As (F) is a single state, it cannot be divided.

The partition of states become

 

P4 = (AC)(E)(BD)(F)

 

As P3 and P4 consist of the same partitions, P3 = (AC)(E)(BD)(F) is the equivalent partition for the machine M.

Minimization: We know that equivalent partition is unique. So, P3 = (AC)(E)(BD)(F) is the unique combination. Here, every single set represents one state of the minimized machine.

Let us rename these partitions for simplification.

Rename (AC) as S1, (E) as S2, (BD) as S3, and (F) as S4.

AC with input 0 goes to (EE) with output 0, and so there will be a transaction from S1 to S2 with output 0. E with input 0 goes to A producing output 0. A belongs to set S1 in the minimized machine, and so there will be a transaction from S2 to S1 with output 0. By this process, the whole table of the minimized machine is constructed.

The minimized machine becomes

Present State
Next State, z
X = 0
X = 1
S1(AC)
S2, 0
S1, 0
S2(E)
S1, 0
S3, 0
S3(BD)
S4, 0
S1, 1
S4(BD)
S3, 0
S2, 1

Example 4.6

Find equivalent partitions and minimize the following finite state machine.

Solution:

Present State
Next State, z
X = 0
X = 1
A
B, 0
H, 1
B
C, 0
G, 1
C
B, 0
F, 1
D
F, 1
C, 1
E
B, 1
C, 1
F
B, 1
B, 1
G
C, 1
B, 1
H
D, 1
A, 1

For string length 0 (i.e., for no input), there is no output. So, all the states are equivalent. It is called 0-equivalent. We can write this as

 

P0 = (ABCDEFGH)

 

For string length 1, there are two types of inputs—0 and 1. The states A, B, and C give output 0 for input 0, and the states D, E, F, G, and H give output 1 for input 0. All of the states give output 1 for input 1.

So, the states in the set P0 are divided into (ABC) and (DEFGH). We can write this as

 

P1 = ((ABC) (DEFGH))

 

Here, A and F are 1-distinguishable because they produce different outputs for input string length 1.

For input string length 2, check the distinguishability by the next state combination.

The states A, B, and C for input 0 produce next states B, C, and B, respectively, and produce next states H, G, F for input 1. The states BCB belong to the same set, and HGF also belong to the same set. So, ABC cannot be partitioned for input string length 2.

The states DEFGH for input 0 produce next states F, B, B, C, D, respectively, and produce next states C, C, B, B, A for input 1. The states B, B, C belong to the same set, but F, D belong to different sets. So, the set (DEFGH) is partitioned into (DH) and (EFG). The new partition becomes

 

P2 = ((ABC) ((DH) (EFG)))

 

The states D and G are 2-distinguishable, because they produce different outputs for input string length 2.

The states A, B, C for input 0 produce next states B, C, B, respectively, and produce next states H, G, F for input 1. The states BCB belong to the same set, but H and G, F belong to different sets. So, the set (ABC) is partitioned into (A) and (BC).

The states B and H produce next states C and D, respectively, for input 0 and produce next states G and A for input 1. C and D belong to different sets, and so the set (BH) is divided into (B) and (H).

The states E, F, G produce next states B, B, and C for input 0 and next states C, B, B for input 1. Both B and C belong to the same set, and so the set (EFG) cannot be partitioned.

The new partition becomes

 

P3 = (((A) (BC)) (((D) (H)) (EFG)))

 

Here, A and B are 3-distinguishable, because they produce different outputs for input string length 3.

By this process, we will get P4 also as

 

P4 = (((A) (BC)) (((D) (H)) (EFG)))

 

As P3 and P4 consist of the same partitions,

 

P3 = (((A)(BC)) (((D)(H)) (EFG)))

 

is the equivalent partition for the machine M.

Minimization: We know that equivalent partition is unique. So, P3 = (((A)(BC)) (((D)(H)) (EFG))) is the unique combination. Here, every single set represents one state of the minimized machine.

Let us rename these partitions for simplification.

Rename (A) as S1, (BC) as S2, (D) as S3, (H) as S4, and (EFG) as S5(A) with input 0 goes to (B), and so there will be a transaction from S1 to S2 with input 0. (A) with input 1 goes to (H), and so there will be a transaction from S1 to S4 with input 1. (BC) with input 0 goes to (BC) for input 0. There will be a transaction from S2 to S2 for input 0. (BC) with input 1 goes to (FG). There will be a transaction from S2 to S5 for input 1.

By this process, the whole table of the minimized machine is constructed.

The minimized machine becomes

Present State
Next State, z
X = 0
X = 1
S1(A)
S2, 0
S4, 1
S2(BC)
S2, 0
S5, 1
S3(D)
S5, 1
S2, 1
S4(H)
S3, 1
S1, 1
S5(EFG)
S2, 1
S2, 1

4.5  Incompletely Specified Machine, Minimal Machine

In real life, for all states and for all inputs, the next state or outputs or both are not mentioned. Those types of machines, where for all states and for all inputs, the next state, or output, or both are not mentioned, are called incompletely specified machine.

In the following machine, for state A and for 00 input, no next state and outputs are specified. So, the previous machine is an example of an incompletely specified machine.

4.5.1  Simplification

An incompletely specified machine can be simplified by the following steps:

  • If the next state is not mentioned for a state, for a given input, put a temporary state T in that place.
  • If the output is not mentioned, make it blank.
  • If the next state and output are not mentioned, put a temporary state T in the place of the next state and nothing in the place of output.
  • Add the temporary state T in the present state column, putting T as the next state and no output for all inputs.

By following the previous steps, the simplification of the previous incompletely specified machine will be

Here ‘T’ is the same as the dead state in finite automata.

Example 4.7

Simplify the following incompletely specified machine.

Solution:

Put a temporary state T in the place of the next state, where the next states are not specified. If the output is not mentioned, there is no need to put any output.

As the temporary state T is considered, put T in the present state column with the next state T for all inputs with no output.

The simplified machine becomes

Minimal Machine: Is the minimum of the machines obtained by minimizing an incompletely specified machine.

In an incompletely specified machine, for all states and for all inputs, the next state, or output, or both are not mentioned. At the time of minimizing the incompletely specified machine, different persons can take the unmentioned next states or outputs according to their choice. Therefore, there is a great possibility to get different equivalent partitions for a single machine. But, we know that equivalent partition is unique for a given machine. It is not possible to find a u nique minimized machine for a given incompletely specified machine most of the times. Therefore, our aim must be to find a reduced machine which not only covers the original machine but also has a minimal (least of the minimum) number of states. This type of machine is called minimal machine, i.e., it is the minimum of the machines obtained by minimizing an incompletely specified machine.

Let us consider the following incompletely specified machine

Present State
Next State, z
X = 0
X = 1
A
E, 1
D, 0
B
E, 0
C, 1
C
A, 0
B, _
D
A, 0
D, 1
E
A, _
B, 0

In this machine, for C with input 1, the output is not specified and the same for E with input 0. There are two types of outputs that can occur in the machine. So, the unspecified outputs can be any of the following:

  1. (B, 0 A, 0)
  2. (B, 0 A, 1)
  3. (B, 1 A, 1)
  4. (B, 1 A, 0).

If it is (a), then the machine and its equivalent partition is

If it is (b), then the machine and its equivalent partition is

If it is (c), then the machine and its equivalent partition is

If it is (d), then the machine and its equivalent partition is

In cases (b) and (d), the number of equivalent partitions are 5, which is equal to the number of states of the machine, i.e., the machine constructed from the equivalent partitions obtained in cases (b) and (d) and the original machines for cases (b) and (d) are the same.

4.6  Merger Graph

In the previous section, it was discussed that minimizing an incompletely specified machine and finding a minimal machine from there is difficult. Sometimes, it is a time-taking assignment if the number of unmentioned next states and outputs are many. For minimizing an incompletely specified machine there is a technique which consist of constructing merger graph and compatible graph and from there finding minimal closed covering.

A merger graph of a machine M of ‘n’ states is an undirected graph defined as follows:

  1. A merger graph consists of n number of vertices, where ‘n’ is the number of states of the machine. That is, in other words, each states of the machine represent one vertex.
  2. There is an undirected arc between a pair of vertices (states) if the outputs do not conflict for those pair of states.
    1. The arc will be an uninterrupted arc if the next states of the two states (vertices) do not conflict.
    2. The arc will be an interrupted arc if the next states of the states (vertices) conflict. The conflicting next states will be placed in the interrupted portions.
  3. There will be no arc between the two vertices if the outputs of the pair of states conflict.

Consider the following examples to construct a merger graph.

Example 4.8

Construct the merger graph for the following machine.

Solution:

In this machine, there are 6 states. So, the number of vertices of the merger graph is 6, namely A, B, C, D, E, and F.

Consider two vertices A and B. In the state table for A and B for input I1, the outputs are 1 and don’t care. It is treated as the same output (don’t care can be either 0 or 1). Similarly, for I2, I3, and I4, the outputs do not conflict. (If the outputs are don’t care, consider it as the same with the other.) So, an undirected arc is drawn between A and B.

For input I4, A produces the next state E, and B produces the next state C. So, the undirected arc between A and B is an interrupted arc and EC is placed in the interrupted portion.

Consider A and C. The outputs do not conflict for inputs I1, I2, I3, and I4. An undirected arc is drawn between A and C. The next states produced by A and C for input I1 are D and E, i.e., conflicting. For input I2, the next states are B and F—also conflicting. The arc is an interrupted arc, and (BF) and (DE) are placed in the interrupted portion.

Consider A and D. For input I2, A and D produce conflicting outputs—0 for A and 1 for B. So, no arc can be drawn between A and D.

Consider A and E. For all the inputs, they produce the same outputs. An undirected arc is drawn between A and E. A and E produce the next states E and A, respectively, for input I4. So, the arc is an interrupted arc and (EA) is placed in the interrupted portion.

Consider A and F. A and F produce conflicting outputs (0 for A, 1 for F) for input I2. So, no arc can be drawn between A and F.

By this process, an uninterrupted arc is drawn between B and C.

An uninterrupted arc is drawn between B and D.

An interrupted arc is drawn between B and E, and AC is placed in the interrupted portion.

An uninterrupted arc is drawn between B and F.

For input I2, C and D produce conflicting outputs. No arc can be drawn between C and D.

For input I3, C and E produce conflicting outputs. No arc can be drawn between C and E.

For input I3, C and F produce conflicting outputs. No arc can be drawn between C and F.

D and E produce the same outputs and the same next states for all the inputs. An uninterrupted arc is drawn between D and E.

D and F produce the same outputs for all the inputs but conflicting next states (B and C) for input I2. An interrupted arc is drawn between D and F, and BC is placed in the interrupted portion.

E and F produce the same output for all the inputs but conflicting next states (A and E) for input I3. An interrupted arc is drawn between E and F, and AE is placed in the interrupted portion.

The final merger graph is shown in Fig. 4.14.

Fig. 4.14

A and B are connected by an uninterrupted, undirected arc.

In the interrupted portion, CE is placed. The connection between A and B will be uninterrupted if C and E are connected by an uninterrupted arc. But there is no arc between C and E. So, there will be no arc between A and B. CE is crossed, therefore.

A and C are connected by an uninterrupted undirected arc. In the interrupted portion, DE and BF are placed. A and C will be connected by an uninterrupted arc if B, F and D, E are connected.

If either ED or BF is not connected, there will be no arc between A and C. But, here, ED and BF are connected.

Example 4.9

Develop the merger graph for the following machine.

Solution:

The number of states of the machine is 5. So, the number of vertices in the merger graph is 5. Let us name them by the name of the states.

Consider two vertices A and B. The states A and B produce the same outputs for all the inputs but different next states for input I2 (conflicting states BD) and for input I3 (Conflicting states BC). So, an interrupted undirected arc is drawn between A and B, and (BC)(BD) is placed in the interrupted portion.

Consider A and C. The two states produce the same outputs for all the inputs. But A and C produce conflicting next states (BD) for input I2. Therefore, between A and C an undirected interrupted arc is drawn, and (BD) is placed in the interrupted portion.

Consider A and D. The states produce the same outputs for all the inputs. But they produce conflicting next states (BC) and (EC) for inputs I1 and I3, respectively. Therefore, an undirected interrupted arc is drawn between A and D and (BC)(EC) is placed in the interrupted portion.

Consider A and E. The states produce the same outputs for all the inputs. But they produce conflicting next states for input I1 and I3. The conflicting next states are (CE) and (BC). An interrupter arc is drawn between A and E, and (CE)(BC) is placed in the interrupted portion.

Consider B and C. They produce the same outputs for all the inputs but conflicting next state pair (BC) for input I3. So, an interrupted arc is drawn between B and C placing (BC) in the interrupted portion.

Consider B and D. No arc is drawn between B and D as they produce different outputs for input I3.

Consider B and E. No arc is drawn between B and E as they produce different outputs for input I3.

Consider C and D. These states produce different outputs for input I3. Therefore, no arc is drawn between C and D.

Consider C and E. These states produce different outputs for input I3. Therefore, no arc is drawn between C and E.

Consider D and E. They produce the same outputs and the same next state combination for all the inputs. Therefore, an uninterrupted arc is drawn between D and E.

The merger graph for the machine is given in Fig. 4.15.

Between C and E, there is no arc. So, the combinations (EC)(BC) placed between A, D and A, E are crossed off. Now, there is no connection between A and E and A and D. There is no arc between B and D. So, the next state combinations (BC) (BD) and (BD) placed between A, B and A, C, respectively, are crossed off.

Fig. 4.15

4.7  Compatibility Graph and Minimal Machine Construction

A compatibility graph is constructed from the merger graph. Before constructing a compatibility graph, we have to know two definitions, namely, compatible pair and implied pair. These are obtained from the merger graph. Without finding the compatible pair and implied pair, a compatible graph cannot be constructed.

4.7.1  Compatible Pair

Two states, say Si and Sj, are said to be compatible, if both of them give the same output strings for all input strings applied to the machine separately, considering Si and Sj as the initial states.

(In the sense of a merger graph, two states are said to be compatible if there exists an uninterrupted arc between the two states.)

4.7.2  Implied Pair

Two states Si and Sj are said to be implied on Sp and Sq if and only if (Sp, Sq) is compatible and then only (Si, Sj) is compatible. The compatibility of (Si, Sj) is dependent on the compatibility of (Sp, Sq). (Sp, Sq) is said to be the implied pair of (Si, Sj).

4.7.3  Compatibility Graph

A compatibility graph is a directed graph constructed as follows:

  • The number of vertices of the compatibility graph corresponds to the number of compatible pairs obtained from the machine.
  • A directed arc is drawn between two compatible pairs (vertices), say from (Si, Sj) to (Sp, Sq) [where (Si, Sj) ≠ (Sp, Sq)] if (Sp, Sq) is the implied pair for (Si, Sj).

The following example describes how to construct a compatible graph.

Example 4.10

Consider the following finite state machine whose compatible graph is to be constructed.

Solution:

To find the compatible pairs, we need to construct the merger graph of the machine first. The merger graph of the machine is given in Fig. 4.16.

The pair of states which are connected by undirected arcs (not crossed in the interrupted portion) are compatible pairs.

The compatible pairs of the given machine are (AB), (AC), (AF), (BC), (BD), (BF), (CE), (CF), and (DE). Therefore, in the compatibility graph there are nine vertices.

In the given machine,

(BD) is the implied pair for (AB). So, a directed arc is drawn from (AB) to (BD).

(CE) is the implied pair for (AF). So, a directed arc is drawn from (AF) to (CE).

(DE) is the implied pair for (BC). So, a directed arc is drawn from (BC) to (DE).

(BD) is the implied pair for (BD). As (Si, Sj) ≠ (Sp, Sq), no arc is drawn from (BD) to (BD).

(AC) and (BF) are implied pairs for (DE). So, two directed arcs are drawn from (DE) to (AC) and (BF).

The compatibility graph for the given machine is given in Fig. 4.17.

Fig. 4.16 Merger Graph

4.7.4  Minimal Machine Construction

To construct the minimal machine, a compatible graph construction is an essential part. After this, we have to find closed compatible, closed covering, and from there minimal closed covering.

A subgraph of a compatibility graph is called closed if, for every vertex in the subgraph, all outgoing arcs and the terminal vertices of the arcs also belong to the subgraph. The pair of states that belong to the subgraph as terminal vertices are called closed compatible.

If a subgraph is closed, and if every state of the machine is covered by at least one vertex of the subgraph of a compatibility graph, then the subgraph forms a closed covering of the machine.

To find a minimal machine, we need to find the subgraphs which closed cover the machine. Then, we need to find the subgraph which contains less number of vertices and which can generate a simpler machine. The states of the minimal machine are the vertices of the subgraph. From these states, the transition functions are constructed. By this process, a minimal machine of the given machine is constructed.

The minimal machine is constructed by the following process for the machine given as an example in the compatibility graph section.

Fig. 4.17 Compatible Graph

4.7.5  Minimal Machine

The subgraphs (AC), (DE), (BF) or (AB), (BD), (AF), (CE) or (AF), (CE), (BC), (DE) are closed subgraphs of the compatibility graph and forms a closed cover of the machine (here every state of the machine is covered by at least one vertex of the subgraph). Among them, the subgraph (AC)(DE)(BF) contains less number of vertices.

In the minimal machine, the states are (AC), (BF), and (DE). Let us rename them as S1, S2, S3, respectively. The minimal machine becomes

Example 4.11

Draw a compatible graph for the following machine. Hence, find the minimal machine.

Solution:

To find the compatible pairs of a machine, we need to construct the merger graph first. According to the rules for the construction of the merger graph, the following graph as shown in Fig. 4.18 is constructed.

Fig. 4.18 Merger Graph

The pair of states which are connected by undirected arcs (not crossed in the interrupted portion) are compatible pairs.

The compatible pairs of the given machine are (AB), (AD), (BC), (BE), (CD), and (CE). Therefore, in the compatibility graph of the previous machine, there are nine vertices.

(CD) is the implied pair for (AB). A directed arc is drawn from (AB) to (CD).

(CD) is the implied pair for (AD). A directed arc is drawn from (AD) to (CD).

(AB) is the implied pair for (BC). A directed arc is drawn from (BC) to (AB).

(AD) is the implied pair for (BE). A directed arc is drawn from (BE) to (AD).

(BE) is the implied pair for (CD). A directed arc is drawn from (CD) to (BE).

The compatibility graph is given in Fig. 4.19.

Fig. 4.19 Compatible Graph

Minimal Machine: In the previous compatibility graph, the subgraph (AD), (CD), (BE) forms a closed covering of the given machine.

The states of the minimal machine are (AD), (CD), and (BE). Let us rename them as S1, S2, and S3, respectively. The minimal machine of this machine is

4.8  Merger Table

The merger table is a substitute application of the merger graph. Similar to the merger graph from the merger table, we can also get the compatible pairs and implied pairs.

If the number of states of a machine increases, the number of combination pair increases. For a machine of n states, the number of two state combinations are nC2, i.e., n(n−1)/2. If n = (n−1), the number of combinations are (n−1) (n−2)/2. The number of combinations increases to (n−1) if the number of states increases from (n−1) to n. It is difficult to connect two states by arcs if the number of states increases. In substitute of that, the merger table is an easier process to find compatible pairs and implied pairs.

4.8.1  Construction of a Merger Table

A merger table can be constructed by the following way.

  • Make a table of (n−1) × (n−1), where the left hand side is labelled by the 2nd state to the nth state and the right hand side is labelled by the 1st state to the (n−1)th state.
  • Each box represents a pair of state combination.
  • Put a cross in the box if the outputs conflict for the pair of states.
  • Put a right sign in the box if the outputs as well as next states do not conflict for the pair of states.
  • If the outputs do not conflict but the next states conflict for the pair of states, put the conflicting next states in the box.

The following examples describe the process in detail.

Example 4.12

Construct a merger table of the following machine and find the compatible pairs.

Solution:

Make a table like the following:

Consider the state combination (AB). Here, the outputs do not conflict but the next states for I2 and I3 conflict. So, the conflicting next state combinations, (BD) and (BC), are placed in the box labelled (AB).

Consider the state combination (AC). Here, the outputs do not conflict but the next states for I2 conflict. So, the conflicting next state combination, (BD), is placed in the box labelled (AC).

Consider the state combination (AD). The outputs do not conflict, but the next states for I1 and I3 conflict. The conflicting next state combinations (CE) and (BC) are placed in the box labelled (AD).

Consider the state combination (AE). The outputs for the states do not conflict, but the next states for input I1 and I3 conflict. (CE) and (BC) are placed in the box labelled (AE).

Consider the state combination (BD). Here, the outputs for input I3 conflict. There will be an × (cross) in the box labelled (BD).

Consider state combination (DE). Here, both the outputs and the next state combination are the same for all the inputs. So a √ (tick) is placed in the box labelled (DE).

By this process, the merger table is

The boxes which are not crossed are compatible pairs. So, the compatible pairs are (AB), (AC), (AD), (AE), (BC), (BD), (BE), (CD), and (DE).

Example 4.13

Construct a merger table of the following machine and find the compatible pairs.

Solution:

For the states AB, for all the inputs, next states and output do not conflict. So a √ (tick) is placed in the box labelled AB.

For states AC, next states and outputs do not conflict for all the inputs. So a √ (tick) is placed in the box labelled AC.

For states AD, the outputs do not conflict, but the next states for input I1 conflict. So, the conflicting next state pair (CE) is placed in the box labelled AD.

In the box labelled (AE), a √ (tick) is placed.

In the box (AF), the conflicting next state pair (BC) is placed.

In the box (BC), the conflicting next state pairs (CF) and (BD) are placed.

In the box (BD), the conflicting next state pair (AE) is placed.

In the box (BE), the conflicting next state pairs (BC) and (CE) are placed.

In the box (BF), the conflicting next state pair (DE) is placed.

The outputs for I2 for the state (CD) conflict. So a × is placed in the box (CD).

In the box (CE), the conflicting next state pair (BF) is placed.

In the box (CF), the conflicting next state pair (BE) is placed.

By this process, the constructed merger table is

The compatible pairs are (AB), (AC), (AD), (AE), (AF), (BC), (BD), (DE), (DF), (CE), (CF), (DE), (DF), and (EF).

4.9  Finite Memory and Definite Memory Machine

If we recall the definition of an FSM, it is told that an FSM is a machine whose past histories can affect its future behaviour in a finite number of ways. It means that the present behaviour of the machine is dependent on its past histories. To memorize the past histories, an FSM needs memory elements. The amount of past input and corresponding output information is necessary to determine the machine’s future behaviour. This is called the memory span of the machine.

Let us assume that a machine is deterministic (for a single state with single input, only one next state is produced) and completely specified. For this type of a machine, if the initial state and the input sequence are known, one can easily find the output sequence and the corresponding final state. One interesting thing is that, this output sequence and the final state are unique. But the reverse is not always true. If the final state and the output sequence are known, it is not always possible to determine uniquely the input sequence. This section describes the minimum amount of past input–output information required to find the future behaviour of the machine and the condition under which the input to the machine can be constructed from the output produced.

4.9.1  Finite Memory Machine

An FSM M is called a finite memory machine of order μ if μ is the least integer so that the present state of the machine M can be obtained uniquely from the knowledge of last μ number of inputs and the corresponding μ number of outputs.

There are two methods to find whether a machine is finite or not

  1. Testing table and testing graph for finite memory
  2. Vanishing connection matrix.

4.9.1.1 Testing Table and Testing Graph for Finite Memory Method

The testing table for finite memory is divided into two halves. The upper half contains a single state input–output combination. If, in a machine, there are two types of inputs and two types of outputs, say 0 and 1, the input–output combinations are 0/0, 0/1, 1/0, and 1/1. Here, 0/0 means 0 input and 0 outputs, that is, for the cases we are getting output 0 for input 0, and 0/1 means 0 input and 1 output, that is, for the cases we are getting output 1 for input 0.

The lower half of the table contains all the combinations of the present states taking two into combination. For four present states, (say, A, B, C, and D) there are 4C2, which is six, combinations: AB, AC, AD, BC, BD, and CD.

The table is constructed according to the machine given.

The pair of the present state combination is called the uncertainty pair. And its successor is called the implied pair.

In the testing graph for finite memory,

  1. The number of nodes will be the number of present state combination taking two into account.
  2. There will be a directed arc with a label of input–output combination, from SiSj [i ≠ j] to SpSq [p ≠ q], if SpSq is the implied pair of SiSj.

If the testing graph is loop-free, the machine is of finite memory. The order of finiteness is the length of the longest path in the testing Graph (l) + 1, i.e., μ = l + 1.

4.9.1.2 Vanishing Connection Matrix Method

If the number of states increases, then it becomes difficult to find the longest path in the Testing graph for finite memory. There is an easy method to determine whether a machine is finite or not, and if finite, to find its order of finiteness. The process is called vanishing connection matrix method.

4.9.2  Constructing the Method of Connection Matrix

  1. The number of rows will be equal to the number of columns (p × p matrix).
  2. The rows and columns will be labelled with the pair of the present state combinations. The labels associated with the corresponding rows and columns will be identical.
  3. In the matrix, the (i, j)th entry will be 1 if there is an entry in the (SaSb) and (SpSq) combination in the corresponding testing table. Otherwise, the entry will be 0.

4.9.3  Vanishing of Connection Matrix

  1. Delete all the rows having 0’s in all positions and delete the corresponding columns also.
  2. Repeat this step until one of the following steps is achieved
    1. No row having 0’s in all positions left
    2. The matrix vanishes, which means there are no rows and columns left.

If the condition 2(a) arrives, the machine is not of finite memory.

If the condition 2(b) arrives, the machine is of finite memory and the number of steps required to vanish the matrix is the order of finiteness of the machine.

The following examples describe the processes in detail.

Example 4.14

Test whether the following machine is of finite memory or not by using testing table–testing graph and vanishing matrix method.

Solution:

Present State
Next State, z
X = 0
X = 1
A
D, 1
A, 1
B
D, 0
A, 1
C
B, 1
B, 1
D
A, 1
C, 1
  • Testing Table and Testing Graph for Finite Memory Method: A table which is divided into two halves is constructed. The machine has two inputs and two outputs. There are four input–output combinations namely 0/0, 0/1, 1/0, and 1/1. The upper half of the machine contains single state input–output combination and the lower half contains two state input–output combinations. There are four states, and so six combination pairs are made. The testing table becomes

    In the testing table, there are six present states combinations. So, in the testing table there are six nodes. There is a directed arc with a label of input–output combination, from SiSj [i ≠ j] to SpSq [p ≠ q], if SpSq is the implied pair of SiSj. The testing graph for finite memory is given in Fig. 4.20.

    (There will be no arc from AB to AA as AA, is the repetition of same state ‘A’.)

    The testing graph is loop-free. The longest path in the testing graph is 5 (CD BC BD AD AC AB), and so the order of definiteness μ = 5 + 1 = 6.

  • Vanishing Connection Matrix Method: According to the rule of the construction of the connection matrix, a table is constructed with six rows and six columns labelled with the present state combinations. In the testing table, (AB) is the next state combination for (AC) for input 1/1. So, an entry 1 is placed in the box labelled (AB)(AC). All the other entries are 0.

Fig. 4.20 Testing Graph for Finite Memory

By this process, the following vanishing connection matrix is generated.

The row labelled AB contains all the entries as ‘0’. So, the row labelled AB and the corresponding column are crossed.

Now, the table does not contain the row and column labelled AB. The row labeled AC contains all ‘0’. So, the row labelled AC and the corresponding column are crossed.

Now, the table does not contain the row and column labelled AC. The row labelled AD contains all ‘0’. So, the row labeled AD and the corresponding column are crossed.

The table does not contain the row and column labelled AD. The row labelled BD contains all ‘0’. So, the row labelled BD and the corresponding column are crossed.

The table does not contain the row and column labelled BD. The row labelled BC contains all ‘0’. So, the row labeled BC and the corresponding column are crossed.

The table does not contain the row and column labelled BC. The row labelled CD contains all ‘0’. So, the row labelled CD and the corresponding column are crossed, which results in the vanishing of the matrix.

The number of steps required to vanish the matrix is 6. So, the order of finiteness μ = 6.

Example 4.15

Check whether the following machine is of finite memory or not by the testing table–testing graph and vanishing connection matrix method.

Solution:

Present State
Next State, z
X = 0
X = 1
A
B, 1
D, 0
B
A, 1
C, 1
C
D, 1
A, 0
D
B, 1
A, 1
  • Testing Table and Testing Graph for Finite Memory Method: A table which is divided into two halves is made. The machine has two inputs and two outputs. There are four input–output combinations namely 0/0, 0/1, 1/0, and 1/1. The upper half of the machine contains single state input–output combination and the lower half contains two state input–output combinations. There are four states, and so six combination pairs are made. The testing table becomes

    In the testing table, there are six present states combinations. So, in the testing table, there are six nodes. There is a directed arc with a label of input–output combination, from SiSj [i ≠ j] to SpSq [p ≠ q], if SpSq is the implied pair of SiSj. The testing graph for finite memory is given in Fig. 4.21.

    Fig. 4.21 Testing Graph for Finite Memory

    The testing graph for finite memory contain two loops AB to AB with label 0/1 and AC to BD with label 0/1, BD to AC with label 0/1. As the testing graph is not loop-free, the machine is not of finite memory.

     

  • Test by Vanishing Connection Matrix Method: In the testing table, six present state pairs are formed. Therefore, the connection matrix consists of six rows and six columns. The rows and columns are labelled with a pair of present state combinations.

    In the matrix, the (i, j)th entry will be 1 if there is an entry in (SaSb) (a ≠ b) and (SpSq) (p ≠ q) combination in the corresponding testing table. Otherwise, the entry will be 0.

    The connection matrix of the previous machine is as follows.

In the previous matrix, the row AD contains all ‘0’. So, the row labelled AD and the corresponding column vanish.

In the modified matrix, there is no row and column labelled AD. The row labelled BC contains all ‘0’. So, the row labelled BC and the corresponding column vanish.

In the modified matrix, there is no row and column labelled BC. The modified matrix becomes

The matrix does not contain any row containing all ‘0’. So, the matrix does not vanish. Therefore, the machine is not of finite memory.

4.9.4  Definite Memory Machine

A sequential machine M is called definite if there exists a least integer μ, so that the present state of the machine M can be uniquely obtained from the past μ number of inputs to the machine M. μ is called the order of definiteness of the machine.

There are three methods to find whether a machine is definite or not.

  1. Synchronizing tree method
  2. Contracted table method
  3. Testing table, testing graph for definiteness method.

4.9.4.1  Synchronizing Tree Method

For a machine with definite memory, only inputs play a role. There is no role of outputs. So, the present state combinations can be divided into two parts for two types of inputs, 0 and 1. Those divided combinations of states can again be divided for input 0 and 1.

If the leaf nodes are of single state, stop constructing the tree. The order of definiteness is the maximum label of the synchronizing tree.

Else, the machine is not of definite memory.

4.9.4.2  Contracted Table Method

  1. Find those present states whose next states are identical.
  2. Represent those present states as single states. (Those present states are equivalent.)
  3. Obtain the contracted table by replacing only one of the present states from the equivalent state set and modify the table according to it.
  4. Repeat steps from (i) to (iii) until new contractions are possible.

By this process, if at last a machine with single state is received, the machine is definite. Its order is the number of steps required to obtain the single state machine.

Else, the machine is not definite.

4.9.4.3  Testing Table, Testing Graph For Definiteness Method

The testing table for definiteness is divided into two halves. The upper half contains the input and the next state combination. The lower half of the table contains all combination of present states taking two into combination. For four present states (say, A, B, C, and D), there are 4C2, which is six, combinations: AB, AC, AD, BC, BD, and CD.

The table is constructed according to the machine given.

For these present state combinations, find the next state combinations for input 0 and input 1.

The pair of present state combination is called the uncertainty pair. And its successor is called the implied pair.

In the testing graph for definite memory,

  • The number of nodes will be the number of present state combination taking two into account.
  • There will be a directed arc with a label of input–output combination, from SiSj [i ≠ j] to SpSq [p ≠ q], if SpSq is the implied pair of SiSj.

If the testing graph is loop-free, the machine is of definite memory. The order of definiteness is the length of the longest path in the testing graph (l) + 1, i.e., μ = l + 1.

The following examples describe the methods to check definiteness.

Example 4.16

Test whether the following machine is definite or not by any of the methods. If definite, find the order of definiteness.

Solution:

Present State
Next State
X = 0
X = 1
A
C
B
B
A
D
C
C
B
D
C
D
  • Synchronizing Tree Method: (ABCD) is the present state combination of the machine. It has two types of inputs, 0 and 1. (ABCD) with input 0 produces the next state combination (CACC). It can be grouped into two distinct states (AC). (ABCD) with input 1 produces the next state combination (BDBD) which can be grouped into (BD).

In the next level, (AC) with input 0 produces a single next state C. With input 1, (AC) produces the single next state B. As C and B are single states, there is no need to approach further to the next level. The state combination (BD) with input 0 produces the next state combination (AC). With input 1, the state combination (BD) produces a single state D. In the next level, the state combination (AC) produces C and B, respectively, for input 0 and 1.

As the leaf nodes are of single state, stop constructing the tree. The order of definiteness is the maximum label of the synchronizing tree in Fig. 4.22. In this case, the order is 3.

Fig. 4.22 Synchronizing Tree

  • Contracted Table Method

    In the previous machine, A and C have the same next state combination (both cases C and B). Therefore, A and C are equivalent states. Among A and C, let us take only A. This means that all the C in the state table are replaced by A. The contracted table is

    Present State
    Next State
    X = 0
    X = 1
    A
    A
    B
    B
    A
    D
    D
    A
    D

    In the table, B and D produce the same next state combination for input 0 and 1. So, B and D are equivalent states. D is replaced by B. The contracted table becomes

    Present State
    Next State
    X = 0
    X = 1
    A
    A
    B
    B
    A
    B

    The table contains two states A and B with the same next state combination for input 0 and 1. So they are equivalent states. B is replaced by A. The contracted table becomes

    Present State
    Next State
    X = 0
    X = 1
    A
    A
    A

    A machine with a single state is received, and the machine is definite. Its order is the number of steps required to obtain the single state machine, here 3.

  • Testing Table Testing Graph Method: A table with two halves is made. The upper half contains the input and next state combinations. The lower half of the table contains all the combination of present states taking two into combination. Here, for four present states (say, A, B, C, and D), there are 4C2, which is six, combinations: AB, AC, AD, BC, BD, and CD. The table is
Present State
0
1
A
C
B
B
A
D
C
C
B
D
C
D
AB
AC
BD
AC
CC
BB
AD
CC
BD
BC
AC
BD
BD
AC
DD
CD
CC
BD

The lower half of the testing table contains six present state combination pairs. The testing graph is given in Fig. 4.23.

The testing graph is loop-free. So, the machine is of definite memory. The longest path of the testing graph is 2 (AB → BD → AC or AD → BD → AC). So, the order of definiteness of the machine is 2 + 1 = 3.

Example 4.17

Test whether the following machine is definite or not by any of the methods (synchronizing tree or contracted table). If definite, find the order of definiteness.

Fig. 4.23 Testing Graph for Definiteness

Solution:

Present State
Next State
X = 0
X = 1
A
D
E
B
A
B
C
C
B
D
C
B
E
A
B
  • Synchronizing Tree Method: The synchronizing tree thus obtained contains the leaf nodes of a single state. So, the machine is of definite memory. The number of levels of the tree, as given in Fig. 4.24, is 3. Therefore, the order of definiteness of the machine is 3.

    Fig. 4.24 Synchronizing Tree

  • Contracted Table Method
    Present State
    Next State
    X = 0
    X = 1
    A
    D
    E
    B
    A
    B
    C
    C
    B
    D
    C
    B
    E
    A
    B

    B and E are producing the same next state combination for input 0 and 1. So, they are equivalent. E is replaced by B. C and D are producing the same next state combination, and D is replaced by C. The contracted table becomes

    Present State
    Next State
    X = 0
    X = 1
    A
    C
    B
    B
    A
    B
    C
    C
    B

    States A and C are producing the same next state combination for input 0 and 1. So, A and C are equivalent. C is replaced by A. The contracted table becomes

    Present State
    Next State
    X = 0
    X = 1
    A
    A
    B
    B
    A
    B

    Both of the states are producing the same next state combination, and so they are equivalent. B is replaced by A.

    Present State
    Next State
    X = 0
    X = 1
    A
    A
    A

    The machine becomes a single state machine. It is of definite memory. The number of steps required to make it a single state machine is 3. Therefore, the order of definiteness of the machine is 3.

4.10  Information Lossless Machine

The main problem of coding and information transmission theory is to determine the conditions for which it is possible to regenerate the input sequence given to a machine from the achieved output sequence. Let us assume that the information used for a coding device in a machine be the input and the coded message be the output achieved, and let the initial and final states be known. It this case, information losslessness of the machine guarantees that the coded message (output) can always be deciphered.

A machine is called information lossless if its initial state, final state, and output string are sufficient to determine uniquely the input string.

A machine is said to be (information) lossless of order μ (ILF-μ) if the knowledge of the initial state and the first μ output symbols is sufficient to determine uniquely the first input symbol.

Let us take a machine M as follows

Present State
Next State, z
X = 0
X = 1
A
A, 1
B, 0
B
B, 0
A, 1

Let the initial state of the machine be A, the final state achieved be A and the coded message (output) be 01. We have to find the information given as input.

Now we are constructing the machine according to the output achieved.

Next State
Previous State, I/P
z = 0
z = 1
A
A, 0
B, 1
B
A, 1
 
B, 0

An output of 01 means that from the reverse side it is 10. The initial state is A and final state is A. So, the diagram will become

The output 1 with the next state A is produced for two cases—previous state A with input 0 or previous state B with input 1.

The output 0 with next state A is produced for no cases. The output 0 with next state B is produced for two cases—previous state A with input 1 and previous state B with input 0.

The initial state is A. In the previous case, A is produced for input 11. Therefore, the input is 11.

Lossy Machine: A machine which is not lossless is called lossy.

Consider the following state table

Present State
Next State, z
X = 0
X = 1
A
A, 1
B, 0
B
B, 1
A, 1

If the testing table obtained from the given machine contains repeated entry of states, the machine is lossy. As an example, for the previous machine, the testing table is as follows

Present State
Next State
z = 0
z = 1
A
B
A
B
AB
AB
AA, AB

The testing table contains repeated entry of states in the form of AA. So, the machine is lossy.

Two states Si,Sj of a machine M are said to be output compatible if there exists some state Sp, such that both Si and Sj are its Ok successor or there exists a compatible pair of states Sa, Sb such that Si Sj are its Ok successor.

Present State
Next State, z
X = 0
X = 1
A
A, 1
B, 0
B
B, 1
A, 1

If we construct an output successor table for it, the table will be

Present State
Previous State, I/P
z = 0
z = 1
A
B, 1
A, 0
B
B, 0
A, 1

Let us apply input 1 and 0, respectively, on states B and A. The next state will be A for both the cases, and the output will be 1 for both the cases. Therefore, we can say A and B are output compatible as there exists a state A such that both A and B are its 1 successor.

4.10.1  Test for Information Losslessness

The process of testing whether a machine is information lossless or not is done by constructing a testing table and a testing graph.

The testing table is constructed in the following way.

  • The testing table for checking information losslessness is divided into two halves. The upper half contains the present states and its output successors.
  • The lower half of the table is constructed in the following way

    – Every compatible pair appearing in the output successor table is taken into the present state column. The successors of these pairs are constructed from the original table. Here, if any compatible pair appears, then that pair is called the implied pair for the compatible pair in the present state column.

    – That new pair is again taken in the present state column if it is not taken.

    – The process terminates when all compatible pairs have been taken in the present state column.

The machine is information lossless if and only if its testing table does not contain any compatible pair consisting of repeated entry.

From the testing table, the testing graph is constructed. The testing graph is constructed in the following way.

  • The number of vertices of the testing graph is equal to the number of output compatible pairs taken in the lower half of the testing table. The labels of the vertices are the compatible pairs in the lower half of the testing table.
  • A directed arc is drawn from vertex SiSj to vertex SpSq (p ≠ q) if SpSq is an implied pair for SiSj.

The machine is information lossless of finite order if the testing graph is loop-free and its order μ = l + 2, where l is the length of the longest path of the testing graph.

Consider the following examples to clarify the method described previously.

Example 4.18

Test whether the following machine is information lossless or not. If lossless, find its order.

Solution:

Present State
Next State, z
X = 0
X = 1
A
C, 1
D, 1
B
A, 1
B, 1
C
B, 0
A, 0
D
D, 0
C, 0

The first step to test whether a machine is lossless or not is to construct a testing table. The testing table is divided into two halves.

Present State
Z = 0
Z = 1
A
CD
B
AB
C
AB
D
CD
AB
(AC)(BC)
(AD)(BD)
CD
(BD)(BC)
(AD)(AC)
 
AC
AD
BC
BD

The testing graph consists of six vertices.

The testing table does not contain any repeated entry. The machine is a lossless machine. The testing graph as shown in Fig. 4.25 does not contain any loop. The order of losslessness is μ = 1 + 2 = 3. The length of the longest path of the graph is 1.

Example 4.19

Find the input string which is applied on state ‘A’ producing the output string 00011 and the final state ‘B’ for the following machine.

Fig. 4.25 Testing Graph for Information Losslessness

Solution:

Present State
Next State, z
X = 0
X = 1
A
A, 0
B, 0
B
C, 0
D, 0
C
D, 1
C, 1
D
B, 1
A, 1

First, we need to prove whether the machine is information lossless. For this, we need to construct a testing table for information lossless.

Present State
z = 0
z = 1
A
AB
B
CD
C
CD
D
AB
AB
(AC)(BC)
(AD)(BD)
CD
(BD)(BC)
(AD)(AC)
AC
AD
BC
BD

The testing table does not contain any repeated entry. So, the machine is information lossless.

Now, we need to construct the output successor table

Present State
z = 0
z = 1
A
A/0, B/1
B
C/0, D/1
C
C/1, D/0
D
A/1, B/0

The input string is applied on state A and has produced output 0. From the output successor table, it is clear that the next states are A or B. By this process, the transition is given in Fig. 4.26.

Fig. 4.26

After traversing the total output string by the output successor table, we have got a state B. So, the input string is 01000.

(Input string retrieval is possible only for an information lossless machine. This can be illustrated in the following example.)

Example 4.20

Find the input string which is applied on state ‘A’ producing the output string 00101 and the final state ‘C’ for the following machine.

Solution:

Present State
Next State, z
X = 0
X = 1
A
B, 0
B, 0
B
C, 0
D, 0
C
D, 0
C, 0
D
A, 0
C, 1

The machine is not information lossless as, in the testing table, for information losslessness, there is a repeated entry BB for the state ‘A’ and output ‘0’. Yet, again we try to find the input sequence by constructing the output successor table.

The output successor table for the given machine is

Present State
Next State, Z
z = 0
z = 1
A
B/0, B/1
B
D/0, D/1
C
D/0, C/1
D
A/0
C/1

The input string is applied on the state A and has produced output 0. From the output successor table, it is clear that the next states are B with input 0 or B with input 1. By this process, the transition is given in Fig. 4.27.

Fig. 4.27

We are getting C as the final state for two input sequences 01101 and 11101. So, we cannot uniquely determine the input string. We can conclude that input string retrieval is not possible for the information lossy machine.

Example 4.21

Test whether the following machine is information lossless or not. If lossless, find its order.

Solution:

Present State
Next State, z
X = 0
X = 1
A
B, 0
C, 0
B
D, 0
E, 1
C
A, 1
E, 0
D
E, 0
D, 0
E
A, 1
E, 1

The first step to test whether a machine is lossless or not is to construct a testing table. The testing table is divided into two halves.

Present State
z = 0
z = 1
A
BC
B
D
E
C
E
A
D
DE
E
AE
BC
DE
AE
DE
AE

The testing table does not contain any repeated entry. The machine is an information lossless machine.

The testing graph for the machine is given in Fig. 4.28.

Fig. 4.28 Testing Graph for Information Losslessness

The testing graph for information losslessness is loop-free. The order of losslessness is μ = 1 + 2 = 3. The length of the longest path of the graph is 1.