Software Testing Methodologies Unit V

UNIT –IV
STATES, STATE GRAPHS, AND TRANSITION TESTING
(1) State Graphs:
(i) States(public question)
 State is a condition or situation during which an object undergoes throughout its life
time.
 States are represented by nodes.
 States are numbered or identified by characters or words or whatever else is
convenient.
 A state graph consists of a set of states in order to represent the behavior of the
system.
 To understand the concept of states let us consider the following examples.
Example 1: A program that detects the character sequence ZCZC can be in the
following states.
1. Neither ZCZC nor any part of it has been detected.
2. Z has been detected.
3. ZC has been detected.
4. ZCZ has been detected.
5. ZCZC has been detected.
Example 2: A moving automobile whose engine is running can have the following
states with respect to transmission.
1. Reverse gear.
2. Neutral gear.
3. First gear.
4. Second gear.
5. Third gear.
6. Four gear.
Example 3: A person’s checkbook can have the following states with respect to bank
balance.
1. Equal.
2. Less than.
3. Greater than.
Example 4: A word processing program menu can be in the following states with
respect to file transmission.
1. Create document. 6. Saving document
2. Copy document. 7. Copy disc.
3. Delete document. 8. Format disc
4. Rename document. 9. Backup disc
5. Compress document. 10. Recover from backup
(ii) Inputs and Transitions:(public question)
 Some thing is modeled and given is called input. Input may be values or variables.
 A state graph takes input provided to states.
 As a result of these inputs the state changes is known as transition.
 That is changing from one state to other state is called transition.
 Transitions are denoted by links that join the states.
 The input that causes the transition is represented on the link. So the inputs are link
weights.
Page 1

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
 A finite state machine is represented by a state graph having a finite number of
states and a finite number of transitions between states.
 The ZCZC detection example can have the following types of inputs.
1. Z
2. C
3. Any character other than Z or C which will be denoted by A.

Page 2

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
A

C,A Z,C,A
A
A,C
Z C Z C
NONE Z ZC ZCZ ZCZC

Z
Z
The above state graph is interpreted as follows.
1. If a system is in the NONE state, and it receives A or C then it is in NONE state only.
2. In NONE state if Z is received, the system enters into Z state. In Z state if it
receives Z it will remain in the same state. If C is received it will go to the ZC
state or if any other character say A is received then it will go back to the NONE
state.
3. In ZC state if it receives Z it will enter into ZCZ state. If C or A is received it
enter into NONE state.
4. In ZCZ state if it receives Z it enter into the Z state. If A is received it enters
into the NONE state.
5. In ZCZ state if it receives C it enter into the ZCZC state. In ZCZC state if it
receives Z or C or A then it will remain in the same state only.
(iii) Outputs:
 Outputs are based on the input values.
 When an input is applied to a state it is processed in order to produce an output.
 Each input and output of the state graph is separated by a slash ‘/’ symbol.
 Outputs are also link weights. If more than one input having the same output
than it can be represented by input1, input 2, input 3…/output.
Example: Let us consider a tape control recovery system. This system contains two
inputs OK & Error. OK means “No write errors”. Error means “There may be write
errors”. The outputs are Rewrite, Erase, None, Out of service. Here None means no
special action is taken.
OK/NONE
OK/NONE
EROR/
EROR/ OUT OF SERVICE
OK/NONE ERASE
1 5 6 7
OK/NONE

EROR/
REWRITE EROR/
OK/NONE 3
ERASE

OK/NONE
EROR/
REWRITE
2 4
EROR/
REWRITE
 At state 1 if no write errors are detected (input = OK) no special action is
taken (output=NONE). If error is detected (input=ERROR) backspace the
Page 3

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
tape one block and rewrite the block (output =REWRITE) i.e. enter into
state 2.

Page 4

www.Jntufastupdates.c
om
 Software Testing Methodologies Unit V
 At state 2 if the rewrite is successful (input= OK) no action is taken
(output=NONE) and return to state 1.
 If the rewrite is not successful try another back space and rewrite
(output=REWRITE) i.e. enter into state 4.
 If there are two successive rewrites and a third error occurs then backspace ten
centimeters and erase (output=ERASE) i.e. from state 4 to state 5.
 If there are two successive rewrites and a third no error occurs then it enter
into state 3 & then state 1. At state 3 if any error is detected then it enter into
state 2 and rewrite.
 At state 5 if the erasure works (input=OK) no action is taken and return to initial
state.
 If it does not work, backspace another ten centimeters and erase. i.e. enter into
state 6.
 At state 6 if the erasure works (input=OK) no action is taken and return to initial
state
 If the second erasure does not work put the tape control out of service i.e enter into
state 7
(iv) State Table:
 If state graph has a large number of states and transitions, then it is difficult to
follow them.
 Therefore a state table is used, as an easiest way to represent all the
states, inputs, transitions and outputs of the state graph.
 A state table is defined as a tabular representation of a state graph.
 It consists of
1. Each row represents a state.
2. Each column represents an input condition.
3. The box at the intersection of row and column represents the next state and the
output.
 The state table for the tape control system is shown below.
STATE OK ERROR
1 1/NONE 2/REWRITE
2 1/NONE 4/REWRITE
3 1/NONE 2/REWRITE
4 3/NONE 5/ERASE
5 1/NONE 6/ERASE
6 1/NONE 7/OUT
7
. (v) Time Versus Sequence:
 State graphs don’t represent time-they represent sequence.
 A transition might take microseconds or centuries.
 A system may be in one state for milliseconds or years.
 The finite state machine model can be elaborated to include notions of time
in addition to sequence, such as Petri nets.
(vi) Software Implementation( public question)
1. Implementation and Operation:
 Here four tables are involved.
1. First table encode the input value. i.e. INPUT_TABLE_CODE.
2. A table that specifies the next state i.e. TRANSITION_TABLE
3. A table that specifies the output. i.e. OUTPUT_TABLE
Page 5

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
4. A table that stores the present state of every device. i.e.
DEVICE_TABLE. This routine operates as follows.
BEGIN PRESENT_STATE:=DEVICE_TABLE
ACCEPT INPUT_VALUE
INPUT_CODE:=INPUT_CODE_TABLE

Page 6

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
POINTER:=INPUT_CODE#PRESENT_STATE
NEW_STATE:=TRANSITION_TABLE
OUTPUT_CODE:=OUTPUT_TABLE
CALL OUTPUT_HANDLER
DEVICE_TABLE:=NEW_STATE
END
Steps:
1. The present state is fetched from memory.
2. The present input value is fetched. If it is numerical it can be used
directly. If it is not numerical encode into a numerical value.
3. The present state and input code are combined.
4. The output table contains a pointer to the routine to be executed.
5. The same pointer is used to fetch the new state value, which is then stored.
2. Input encoding and Input Alphabet:
 Only the simplest finite state machines can use the inputs directly.
 In ZCZC detector there are 256 possible ASCII characters. But we are
taken Z, C and OTHER.
 The input encoding here is for OTHER=0, for Z=1, for C=2.
 The different encoded input values are called the input alphabet.
3. Output encoding and Output Alphabet:
 A single character output for a link is rare.
 So we want to output a string of characters.
 These can be encode into a convenient output alphabet.
4. State codes and State-Symbol products:
 The term state-symbol product is used to convert the combined state and
input code into a pointer to compact table.
5. Application Comments for Designers:
 An explicit state table implementation is advantageous when either the
control function is likely to change in the future or when the system has
many similar, but slightly different control functions.
6. Application Comments for Testers(Public Question)
 Independent testers are not usually taken with either implementation
details or the economics of this approach.
 If the programmers have implemented an explicit finite state machine then
much of our work has been done for us.
 Sometimes showing the programmers the kinds of tests developed from a
state graph description can lead them to consider it as an implementation
technique.
(2) Good State Graphs and Bad State Graphs:
(i) General:
 In testing we deal with a good state graph and also with a bad one.
 The following figure shows examples of improper or bad state graphs.
1 1,2

2
A B In state B the initial state can never be entered again

Page 7

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
1 1,2 1

2
2
A B C
1,2
1,2 1,2

A B

1 1

2
A B

1 2

1,2
A B
1
(2) State Bugs
 The bugs in states are called state bugs. The state bugs arise due to the following
reasons.
1. Number of States:
 A State graph consists of the number of states. It represents behavior of the
system.
 In practice the state is directly or indirectly recorded.
 State table is used to record the number of states of the state graph.
 In state table the state bugs are occurred because of missing states.
 That is in state table if the number of states are not recorded or missed
then the result might be the bugs.
 To find the missing states, first find the number of states
 The number of states is founded by as follows.
1. Identify all the component factors of the state.
2. Identify all the allowable values for each factor.
3. Now the number of states is the product of the factors and allowable
values.
 Functional specifications are used to find the factors of the state.
They may also helpful to find the number of possible values for each
factor.
2. Impossible States:
 A state that is not possible is called impossible states.
 For example a broken engine cannot run, so running a broken
engine state is impossible state.
 There are some combination of factors that are impossible,
they are GEAR: R, N, 1, 2, 3, 4 = 6 factors

Page 8

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
DIRECTION: forward, reverse, stopped = 3
factors ENGINE: running, stopped = 2
factors TRANMISSION: ok, broken = 2
factors
ENGINE: ok, broken = 2 factors

Page 9

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
TOTAL = 6 x 3 x 2 x 2 x2 =144 states.
 A broken engine cannot run so the combination of engine is 3 states.
Therefore the total number of states is 108. A car with a broken
transmission does not move for long, there by further decreasing the
number of states.
3. Equivalent States:
 Two states A, B are equivalent if every sequence of inputs starting from
one state (s) produces exactly the same sequence of outputs.
 Let us take an example of two equivalent states.
 In the below figure, let us assume the system is in state S.
 An input of ‘a’ begins a transition to state A and an input of ‘b’ begins a
transition to
state B from S.
 If all the sequence of inputs from the state A generates exactly the same
sequence of outputs as the other state B, then we say that these two
states are equivalent.

A
a

S C

b
B

 Because these two states are treated equally, the state graph can be
minimized by combining these two equivalent states as shown in the
following figure.

a,b
S A,B C

 Equivalent states can be recognized by the following procedure.

1. The two states are differentiated only by the different input values.
For example Consider the following figure.
d/y

e/y
A C
a
e/y
1
e/x
b
e/x
B C

Page 10

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
d/y
Here except a, b inputs, the system behavior in two states A, B are identical
for every input sequence.

Page 11

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
2. There are two set of rows which except for the state name, have identical
state graphs with respect to transitions and outputs. The two sets can be
merged. Let consider the following equivalent states.
a/y
a/u

b/x b/u
A1 A2 A3
a/u

1 a/w b/y
a/w
b/y
b/u
b/x
B1 B2 B3
b/u

a/y
a/u
The Decision table to the above figure is shown
below:
STATE OK ERROR
1 A1/u B1/u
A1 A1/y A2/x
B1 B1/y B2/x
A2 B2/w A3/u
B2 A2/w B3/u
A3 A3/u B2/y
B3 B3/u A2/y
The merged equivalent states are represented by as follows
a/y a/w a/u

b/x b/u
a/u,b/u
1 A1 B1 A2 B2 A3 B3

b/y
The Unmergeable states are represented by as follows
a/y a/w
a/u

b/x b/u
A1 A2 A3
a/u

1
b/y
b/u
b/x
B1 B2 B3
b/u

a/y
a/w a/u
(3) Transition Bugs( public question)
 The connectivity between two or more states is known as transition.
 The bug in transition is called Transition Bug.
1. Unspecified and Contradictory Transitions:
 A transition is specified between states. If a transition may occur between
states and not specified (i.e. unspecified transition) then the transition
Page 12

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
bug occurs.
 If a transition is not possible in the state then there must be a method
that prevents the occurrence of input in that state.

Page 13

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
 If there is no such method available then the occurrence of input becomes
inefficient.
 So to avoid transition bug one transition must be specified for every
input state combination.
 A program does not contain contradictions, if one input must be processed
at a time to produce desired output. If a transition does not possible
between states and the transition is specified then a contradictory
transition may occur.
 That is if a programmer does not take all the measures of a program then
contradictory transitions may occur because of transitions may not be
possible between some of the states. For example if a single bit of a state
is misplaced by the programmer then it doubles the number of states in
the state graph and performs the contradictory transitions. This
contradiction gives a transition bug.
2. Example
 The following example shows how to convert a specification into a state
graph and how contradictions can come out.(public question)
OK

ERROR ERROR ERROR ERROR ERROR

0 1 2 3 4 5

Rule 1:
 The program will maintain an error counter which will be incremented
whenever there is an error. Here there are only two input values OK, ERROR.
 These values make it easier to detect ambiguities and contradictions in a state
table.
INPUT
STATE OK ERROR
0 0/NONE 1/
1 2/
2 3/
3 4/
4 5/
5 6/
6 7/
7 8/
Rule 2:If there is an error rewrite the block.
INPUT
STATE OK ERROR
0 0/NONE 1/REWRITE
1 2/REWRITE
2 3/REWRITE
3 4/REWRITE
4 5/REWRITE
5 6/REWRITE
6 7/REWRITE
7 8/REWRITE
Rule 3: If there are three errors, erase 10 centimeters of tape and rewrite the block.
INPUT
STATE OK ERROR
Page 14

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
0 0/NONE 1/REWRITE
1 2/REWRITE
2 3/REWRITE,ERASE,REWRITE
3 4/REWRITE,ERASE,REWRITE
4 5/REWRITE,ERASE,REWRITE
5 6/REWRITE,ERASE,REWRITE
6 7/REWRITE,ERASE,REWRITE
7 8/REWRITE,ERASE,REWRITE
Rule 4: If there are three erasures and another error occur, then put out of service.
INPUT
STATE OK ERROR
0 0/NONE 1/REWRITE
1 2/REWRITE
2 3/ERASE,REWRITE
3 4/ERASE,REWRITE
4 5/ERASE,REWRITE
5 6/OUT
6
7
Rule 5:
 If the erasure was successful return to the normal state and clear the error
counter.
INPUT
STATE OK ERROR
0 0/NONE 1/REWRITE
1 2/REWRITE
2 3/ERASE,REWRITE
3 0/NONE 4/ERASE,REWRITE
4 0/NONE 5/ERASE,REWRITE
5 0/NONE 6/OUT
6
Rule 6:
 If the rewrite was unsuccessful increment the error counter, and try another
rewrite.
Rule 7:
 If the rewrite was successful decrement the error counter and return to the
previous state. INPUT
STATE OK ERROR
0 0/NONE 1/REWRITE
1 0/NONE 2/REWRITE
2 1/NONE 3/ERASE,REWRITE
3 0/NONE 4/ERASE,REWRITE
2/NONE
4 0/NONE 5/ERASE,REWRITE
3/NONE
5 0/NONE 6/OUT
4/NONE
6
Rule 7 A:
Page 15

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
 If there have been no erasures and the rewrite is successful return to the
previous state.

Page 16

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
3. Unreachable States:
 An un reachable state is like unreachable code If a transition is not
specified between two states then that states are unreachable. That is if
any incorrect transition occurs then the state becomes unreachable.
 There may be a transition from unreachable states to other states.
4. Dead States:
 A dead state is a state that once entered cannot be left.
 In programming, a set of states may be dead because a program has two
stages.
 In the first stage an initialization process takes place that consists of
number of states to be initialized.
 In the second stage strongly connected set of functional states takes
place in which operations of the states cannot be completed. So the
functional states become dead states. The only solution to this problem is
system restart.
(4) Output Errors:
 The errors in output are called output errors.
 The states, the transitions, and the inputs may be correct & there may be
no dead or unreachable states, but the output for the transition may be
incorrect.
 Output actions must be verified independently for states and transitions.
(5) Encoding Bugs:(public question)
 Encoding is a process of converting or coding the inputs, transitions, and outputs of
the state.
 Encoding process is applied in both explicit and implicit finite state machines.
 The encoding bugs are more common at the time of input coding, output
coding and state coding in an explicit state machine.
 The encoding bugs may also exist in an implicit finite state machine, because
of different views made by programmer and tester.
 The behavior of a finite state machine is invariant under all encodings.
 That is say that the states are numbered 1 to n.
 If you renumber the states by an arbitrary permutation, the finite state machine
is unchanged. Similarly for input and output code is unchanged.
 Therefore if you present your version of the finite state machine with a different
encoding and if the programmer objects to renaming then there is encoding
bugs.
 You may have to look at the implementation for these, especially the data
dictionary.
 The implementation of the fields as bunch of bits tells you the potential size of the
code.
 If the number of code value is less than this potential, there is an encoding process.
 In strongly typed languages with user defined semantic types the
encoding process is probably a type conversion a set membership to
integer.
 Again you may have to look at the program to spot potential bugs of this kind.
(3) State Testing:
(i) Impact of Bugs:
 Let us say that a routine is specified as a state graph that has been verified as
Page 17

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
correct in all details.
 From the following the bugs may occur.
1. Wrong number of states
2. Wrong transition
3. Wrong output for a given transition
4. Pair of states are wrongly made equivalent
5. Set of states are split to create in equivalent duplicates.
6. Set of states become dead.

Page 18

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
7. Set of states become unreachable.
(ii) Principles:
 State testing is defined as a functional testing technique to test the
functional bugs in the entire system.
 The principles for state testing are very similar to the principles of path testing.
 For path testing it is not possible to test every possible path in a flowgraph.
 Similarly for state testing it is not possible to test every possible path in a state
graph.
 In a state graph a path is a sequence of transitions caused by a sequence of inputs.
 In state testing the primary interest is given to the states and transitions rather than
outputs.
 In state testing define a set of covering input sequences and for each step in
each input sequence define the expected next state, the expected transition
and the expected output code.
 A set of tests consists of three sets of sequences
1. Input sequences.
2. Corresponding transitions
3. Output sequences.
(iii) Limitations and extensions:
The limitation is: State transition coverage in a state graph does not guarantee complete
testing. The extension:
 Chow defines a hierarchy of paths and methods for combining paths.
 The simplest is called a 0 switch which corresponds to test each transition
independently.
 The next level consists of testing transition sequences consisting of two
transitions called 1 switch. The maximum length switch is an n-1 switch where
n is the number of states.
The different advantages are
 State testing is useful when the error corrections are less expensive.
 State testing is also useful when the testers want to detect a specified input.
 A state testing is specifically designed for catching the deep bugs.
 A state testing provides easiness during the design
of tests. The different disadvantages are
 State testing does not provide through testing because when a test is completed
there might be some bugs remains in the system. Testers require large number
of input sequences to catch transition errors, missing states etc..
(iv) What to model:
 Combination of hardware & software can be modeled sufficiently complicated state
graph.
 The state graph is behavioral model that is it is functional rather than structural.
(v) Getting the data:
 Here labor intensive data gathering is needed and needs more meetings to resolves
issues.
(vi) Tools:
 Tools for hardware logic designs are needed.
(4) Testability tips:
(i) A balm for programmers:
 The key to testability design is easy that is we can easily build explicit finite state
machines.
Page 19

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
(ii) How big How small:
 For two finite state machines there are only eight good and bad ones.
 For three finite state machines there are eighty possible good and bad one.
 Similarly for Four state machines 2700 most of which are bad and for five state
machines 275000 most of which are bad. For six state machines 100 millions
most of which are bad.
(iii) Switches, Flags and unachievable paths :
 The functionality of switches and flags are almost similar in the state testing.

Page 20

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
 Switches or flags are used as essential tool for state testing to test the finite
state machine in every possible state.
 A flag or switch value is set at the initial process of finite state machine, and then
this value is evaluated and tested.
 Depending on its value the specific path is selected to find an easiest way for
testing the finite state machine.
 Mostly the switch or flag works on true or false condition.
 In figure a flag is set to p in the program. This p variable is assigned to some
value which can be evaluated.
 Depending on its value a path is separated into branches in order to proceed
testing in either way that is u or x
 This also can be done by removing a flag and separating v path into two
different paths w,y as shown in the above figure.
 Unachievable paths those paths which don’t interact with each other.
 Here there are four paths u,w,x,y in that two are not achievable and two are
achievable.
 That is u is not achievable to path y and path x is not achievable to path w & u
is achievable to path w and path x is achievable to path y.
 Finally both the paths uw and xy are needed to cover the branches.
 In the above figure there are three flag variables p,q,r in the program.
 These variables are assigned some values that can be evaluated and based
on which the paths are separated into branches.
 The main benefit of using this implementation is to remove the unnecessary
combination from the decision tree as shown in the figure c.
(iv) Essential and inessential finite state behavior:
 To understand an essential and inessential finite state behavior, we need
to know the concept of finite state machines and combinational machines.
 There is a difference between finite state machines and combinational
machines in terms of quality.
 In combinational machines a path is chosen depending on the truth values of
predicates.
 The predicate truth values are the values which once determined will never
change and always remains constant.
 In these machines a path is equivalent to a Boolean algebraic expression over the
predicates
 Further more it does not matter in which order the decisions are made.
(v) Design guide lines:
 Fine state machine is represented by a state graph having a finite number of
states and a finite number of transitions between states
 Finite state machine (FSM) is a functional testing tool and programming testing tool.
 That is it is an essential tool for state testing in order to identify or model
the behavior of software.
 The different guide lines are given below.
1. Initially learn the procedure of finite state machine that are used in both
hardware and software.
2. Design an abstract machine in such a way that it works properly and
satisfies the user requirements.
3. Design an explicit finite state machine.
4. Prototype test must be conducted thoroughly to determine the processing
Page 21

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
time and space of explicit finite state machine design.
5. If time or space is more effecting the overall system, then use shortcuts to
complete the design process.

Page 22

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
6. If there are more than a few numbers of states then use hierarchical design
to represent them.
7. If there is large number of states then software tools and programming
languages must be developed.
8. The capability to initialize to an arbitrary state must be inbuilt together with
the transition verification instrumentation.

UNIT -V
GRAPH MATRICES AND APPLICATIONS
(1) Motivational Overview:
(1) What are the problems with pictorial graphs?
Problems with pictorial graphs:
1. Tracing a path in a pictorial graph is difficult task.
2. There is every possibility of having an error while tracing i.e. we can miss a
link or cover some links twice.
3. Even yellow marking pen also not be reliable because once the concentration is
lost during marking; we will lose the position to be marked.
4. It is very difficult to generate test cases for a pictorial graph
5. The time is also wasted if pictorial graphs are used.
(2) What are the graph matrices and their applications?
(i) Graph Matrices:
 The matrix in which every node of a graph is represented by one row and
one column is called a graph matrix. or The matrix that represents the
structure of a graph is known as graph matrix.
 In a graph matrix each row and each column intersection represents, the
relationship between the respective row nodes and column nodes.
 A graph is an abstract representation of a software structure.
 A graph can be traced thoroughly to perform a check for covering paths,
sensitizing paths, predicate expressions etc.
 Here we use either pictorial graphs or graph matrices.
 Tracing a path in a pictorial graph is difficult task.
 There is every possibility of having an error while tracing i.e. we can miss a
link or cover some links twice. Even yellow marking pen also not be reliable
because once the concentration is lost during marking; we will lose the
position to be marked.
 Graph matrices are introduced to overcome these problems.
 A graph matrix is purely based on matrix methods.
(ii) Applications:
(i) Tool Building:
 Using matrix representation and its methods we construct test tools.
 It is more difficult to generate test cases for a pictorial graph than the graph
matrix.
(ii) Doing and understanding testing theory:
 Theoretically speaking, graphs are the simple structures but when used in
theorem proving we use graph matrices because pictorial graphs will omit
some important algorithms.
(iii) The Basic Algorithms:
Page 23

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
 The basic algorithms represent a basic tool kit. The basic tool kit consists of
1. Matrix multiplication is used to derive the path expression from every node to
every other node.
2. A partitioning algorithm is used for eliminating loops from graphs.
3. A collapsing process is used to get the path expression.

Page 24

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
(3) Write relative merits and demerits of different Graph Matrix representations?
(i) Merits:
1. Using matrix representation and its methods we construct test tools.
2. Matrix representation gives the best results.
3. Graph matrices are used for developing algorithms and proving theorems of
graphs.
4. Linked list representation is used to represent graph matrices.
(ii) Demerits:
1. Graph matrix representation for two dimensional arrays is useful only for
small graphs with simple link weights, however with large graphs; this
matrix representation gives inconvenience.
2. Matrix representation requires a large storage space.
3. An additional weight matrix is also needed.
4. Since many entries of the graph matrices are null, the time taken to process
such entries is a waste of time.
(2) The Matrix of a graph:
(1) Explain about the matrix of a graph?
(i) Basic Principles:
 A graph matrix is array representation of nodes. In a graph matrix each row
and each column intersection represents, the relationship between the
respective row nodes and column nodes.
 Some examples of graphs and their associated matrices are given by.
a a
a
a a b
1 [0] 1[a] 1 2 b 2
1
Figure (a)
Figure (b) Figure (c) Figure (d)

a 3 1 2 3 4
e
2 b 1 a c
b1 a
1 2 a 3 d 2
1 2
1 b+c 3 b
d c
2 c c d 4 d
3 3 4

Figure (e)
Figure (f)
d
1 2 4 5
a b c 3
1 3 4 2 a
f 1
e g 2 d b
5 3 c f
h 4 g e h
5

Figure (f)

Page 25

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
1 2 4 5 6 7 8
3
1 a i
2
3 b h
h
3 4 j
c g
a b 5 m
m d e f c l d
1 5 6 7 8 2 6
e
i l 7
j f k g
4 k 8
Figure (h)
 Now observe the
following
1. The size of the matrix is equal to the number of nodes.
2. There is a place to put every link weight between any node and any other
node. i.e. The entry at a row and column intersection is the link weight of the
link.
3. A connection from node i to node j does not same that a connection from node j
to node
i. For example in figure (h) the (5,6) entry is m but the (6,5) entry is c..
(ii) A simple weight:
 Let ‘1’ means that there is a connection and ‘0’ means that there is no connection.
 The different arithmetic rules are
1+1=1 1+0=1 0+0=0
1x1=1 1x0=0 0x0=0
 A matrix with link weights defined with 1 or 0 is called a connection matrix.
 Consider the following flowgraph and its matrix representation.
1 2 34 5 6 7 8
1 1 1 2-1=1
2
3 1 1 2-1=1
1
3 4 1 1-1=0
1 1
1 1 5 1 1-1=0
1 1 e 1 1 1 1
1 5 6 7 8 2 6 3-1=2
1
1-1=0
1 1 7
1 1 1 1
4 1 8 3-1=2

6+1=7
 Each row of a matrix denotes the outlinks corresponding to that node and
each column denotes the inlinks corresponding to that node.
 A branch node is a node with more than one non zero entry in its row. For
example rows 1,3,6, and 8 of the above figure have more than one entry, so
these nodes are branch nodes.
 A junction node is a node with more than one non zero entry in its column.
For example columns 5,6 and 7 of the above figure have more than one
entry, so these nodes are junction nodes
 By subtracting 1 from the total number of entries in each row and ignoring
rows with no entries we obtain the number of decisions for each row. Adding
these decision values and then adding 1 to the sum gives the graph’s
Page 26

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
cyclomatic complexity.
 In the above figure the graph’s cyclomatic complexity is 7.
(iii) Further notation:
 The link weight between node i and node j, is denoted by aij.

Page 27

www.Jntufastupdates.c
om
 Software Testing Methodologies Unit V
 A self loop at node i is denoted by aii The link weight for the link between
nodes j and i is denoted by aji.
 Consider the following figure.
h
3 c g
a b
d e f
1 6 7 8 2
5
i j l
4
 From the above figure
abmd=a13 a35 a56 a67
degef=a67 a78 a87 a78 a82
ahekmlld=a13 a37 a78 a85 a56 a66 a66 a67
 The expression aij ajj ajm denotes that a path from node i to j, with a self loop at
j and then a link from node j to m.
 The transpose of a matrix is the matrix with rows and columns interchanged.
 It is denoted by AT.
 If C=AT then cij=aji
 The intersection of two matrices is denoted by A#B. If C=A # B then cij=aij # bij.
(3) Node Reduction Algorithm:
Write the steps involved in Node Reduction Algorithm. Illustrate with an
example? Node Reduction Algorithm:
Steps:
1. The reduction is done one node at a time by combining the elements in the last
column with the elements in the last row and putting the result into the entry at
the corresponding intersection. This step is called cross-term reduction. After
cross term reduction the matrix size is reduced by one.
2. If there is one entry in one position and we want to enter another entry in that
same position then add that two entries. This step is called parallel reduction.
3. If there is entry in principle diagonal then it represents a self loop. To remove
that self loop, multiply every term in that row by the loop term. This step is
called loop reduction.
4. By using the above three steps a 2x2 size matrix is obtained with the path
expression. This path expression is the required path expression from node 1
to node 2.
Example:
 Consider the following flow graph.
d
1 a 3 b 4 c 2

f g
e
5
h
 Specify the above flowgraph in the matrix format.
1 2 3 4 5
1 . a
2 .
3 d . b
c . f Page 28
g e h
www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
4
5

Page 29

www.Jntufastupdates.c
om
 Software Testing Methodologies Unit V
 Remove the self loop at node 5 by applying the loop reduction step.
1 2 3 4 5
1 . a
2 .
3 d . b
4 c . f
5 h*g h*e .
 Combine the elements in the last column with the elements in the last row
by applying cross-term reduction and parallel reduction steps.
1 2 3 4
1 . a
2 .
3 d . b
4 c+fh*g fh*e .
 Combine the elements in the last column with the elements in the last row
by applying cross-term reduction and parallel reduction steps.
1 2 3
1 . a
2 .
3 d+b(c+fh*g) bfh*e

 Again a self loop occurred at node 3. So Remove the self loop by applying
loop reduction step.
1 2 3
1 . a
2 .
3 (bfh*e)*(d+b(c+fh*g))

 Combine the elements in the last column with the elements in the last row
by applying cross-term reduction.
1 2
.
1 a(bfh*e)*(d+b(c+fh*g))

2 .
Note: Refer other four examples from class notes
(4) Applications:
(1) Illustrate the applications of Node Reduction Algorithm:
(i) Maximum Path Count Arithmetic:
 For theory refer unit-5 material.
 For example refer unit-8 notes.
(ii) Probability of path expressions:
 For theory refer unit-5 material.
 For example refer unit-8 notes.

Page 30

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V

(5) Relations:
(1) What is a Relation? What are the different properties of
Relations? Relation:
 The property by which two nodes are interconnected is called a relation.
 A relation can be represented by a link with connecting nodes.
 A link represented with link weight.
 This link weight can be numerical, logical, illogical, or whatever.
 The graph matrix which consists of unweighted simple links is called a connection
matrix
 The graph matrix which consists of weighted simple links is called a relation
matrix.
Different properties of relations:
 The different properties of relations are.
(i) Transitive Relations:
 A Relation R is transitive if aRb and bRc then aRc.
 Examples of transitive relations are: is connected to, is greater than or equal to,
is less than or equal to, is a relative of, etc.
 Examples of intransitive relations are: is a friend of, is a neighbor of, etc.

(ii) Reflexive Relations:

 A relation R is reflexive if for every a, aRa. This relation represents a self-
loop at every node.
 Examples of reflexive relations are: equals, is a relative of, etc.
 Examples of irreflexive relations include: not equals, is a friend of, etc.
(iii) Symmetric Relations:
 A relation R is symmetric if aRb then bRa. This relation represents if a link from
a to b then there is also a link from b to a.
 A graph whose relations are symmetric is called an undirected graph and a
graph whose relations are not symmetric is called a directed graph
 Examples of symmetric relations are: a relative of, is brother of, etc.
 Examples of asymmetric relations are: is the boss of, is greater than, etc.
(iv) Antisymmetric Relations:
 A relation R is antisymmetric, if aRb and bRa, then a = b.
 Examples of antisymmetric relations are: is greater than or equal to, is a subset of,
etc.
 Examples of nonantisymmetric relations are: is connected to, is a relative of, etc.
(2) What are Equivalence Relations and Partial Ordering Relations?
(i)Equivalence Relations:
 A relation is said to be an equivalence relation if it satisfies transitive,
reflexive, and symmetric properties. If a set of objects satisfy an
equivalence relation, then it forms an equivalence class.
 The idea behind a partition-testing is that we can partition the input space into
equivalence classes.
(ii)Partial Ordering Relations:
 A partial ordering relation satisfies the reflexive, transitive, and antisymmetric
properties.
 A graph which shows partial ordering relation between its nodes is said
to be partial ordered graph. Partial ordered graphs have different
Page 31

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
properties. They are
i. loop free,
ii. There is at least one maximum element.
iii. There is at least one minimum element.

Page 32

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
iv. If you reverse all the arrows the resultant graph is also partial ordered.
 The maximum element ‘a’ represents the relation xRa. Similarly, the minimum
element ‘a’, represents a relation aRx. Examples are Trees and loop-free
graphs.
(6) The Powers of a Matrix:
(i) Explain about Matrix Powers and
Products? Matrix Powers and Products:
 A graph matrix is array representation of nodes. In a graph matrix each row
and each column intersection represents, the relationship between the
respective row nodes and column nodes.
 The square of the matrix represents all path segments with two links long.
Similarly the third power represents all path segments with three links long
and so on.
 Let A be a matrix whose entries are aij. The set of all paths between any
node i and any node j is given by
n n n n n n
aij + aik akj + aik akmamj + aikakmaml alj
M

M
M

M
k=1 k=1 m= k=1 m=1 l=1
1

+. ..
n n
n n
.. aikakmaml . . . aqp apj
M
M

M
M

.
k=1 m=1 l=1 p=1
 Given a matrix whose entities are aij the square of that matrix is given by
n
aij = aik akj
M

k=1
 When given two matrices A,B with entries aik and bkj respectively. The
product of AB is a new matrix C whose entries are cij.
n
cij = aik bkj
M

k=1

a11 a12 a13 a14 b11 b12 b13 c11 c12

b14 c13 c14
a21 a22 a23 a24 b b22 b23 c21 c22 c23
a31 a32 a33 a34 x 21 =
b24 b31 c24 c31
a41 a42 a43 b32 b33 c32 c33
a44 b34 c34
b41 b42 b43 b44 c41 c42 c43 c44
c11 = a11b11+ a12 b21 + a13 b31 +
a14 b41 c12 =a11b12 + a12 b22 + a13
b32 +a14b42 c13 =a11b13+a12 b23 +
a13 b33 + a14b43
c32 = a41b12+ a42 b22+a43 b32 + a44 b42
c44 = a41b14 +a42 b24 +a43b34+ a44 b44
 The c32 entry is obtained by combining, the entries in the third row of the A
matrix, with the corresponding elements in the second column of the B matrix.
Example:
Page 33

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
 Consider the following flowgraph and its graph matrix.
d
1 2 3 4 5
a b c
1 3 4 2 1 a
f 2
e g Let A = 3 d b
5 4 c f
5 g e h
h .

Page 34

www.Jntufastupdates.c
om
 Software Testing Methodologies Unit V
A2 = A * A
1 2 3 4 1 2 4 5 1 2 3 4 5
5 a 3 1 ad ab
1 1 a2
A2 2
d b 2 bc bf
= = 3
3 c f x 3 d b fg fe fh
4
4 g e h 4 c f ed+hg he eb
5 h2
5 5 g e h

A3 = A2 * A
1 2 3 4 1 2 3 4 1 2 3 4 5
5
ad ab 5 1 abc abf
1
1 a 2
2 bc bf2
bfg bfe bfh
fg fe fh d b
A = 3
3
x 3 = 3 fed+fhg fhe feb fh2
ed+hg he eb h2 c f
4 4 4 hed+ebc+h2g h2e heb ebf+h3
g e h
5 5 5

(ii) Explain about the set of all paths and the algorithm for finding set of all paths?
(a) The set of all paths:
 The set of all paths is given by the following infinite series of matrix powers.
∞
∑ Ai = A1+A2+A3+…+A∞
i=1
 Let I be an n x n diagonal matrix where n is the number of nodes, then
the above expression becomes
∞
∑ Ai = A(I+A1+A2+A3+…+A∞)
i=1
 We know that (A+A) = A
So (A+I)2 = A2 + 2AI + I2 = A2 + 2A + I2 = A2 + A+A + I2= A2+A+I. (Since A +
A = A)

 Similarly
(A+I)n = I+A1+A2+A3+…An
 Now the original expression becomes
∞
∑ Ai = A(I+A1+A2+A3+…+A∞) = A(A+I)∞
i=1
 If the paths of length n-1, where n is the number of nodes, the set of all such paths
is

n-1
∑ Ai = A(A+I)n-2
i=1
(b) The algorithm for finding set of all paths:
 The algorithm for finding set of all paths
1. Express n-2 as a binary number.
2. Calculate the successive squares of (A+I) matrix, that is (A+I)2, (A+I)4,
(A+I)8, (A+I)16 and so on.
Page 35

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
3. Select only the binary powers of (A+I) matrix that correspond to a value 1
in the binary representation of (n-2).
4. The set of all paths of length less than or equal to (n-1) is obtained from
the original matrix as a result of step 3.

Page 36

www.Jntufastupdates.c
om
 Software Testing Methodologies Unit V
 For example the set of all paths for 16 nodes is
given by 15
∑ Ai = A(A+I)8(A+I)4(A+I)2
i=1
 A matrix for which A2=A is said to be idempotent matrix. A matrix whose
successive power gives an idempotent matrix is called idempotent generator.
The nth power of a matrix A + I over a transitive relation is called the transitive
closure of the matrix.
(iii) What are the loops? How to convert graphs with loops into loop-free graphs:
 Loops are infinite sum of matrix powers.
 The way to handle loops is similar like handling loops in regular expressions.
 Loop terms are displayed on the principle diagonal of the graph matrix. A
loop can be removed from a graph by using loop reduction step of Node
Reduction Algorithm.
Example:
 Consider the following flowgraph and its graph matrix
d
a b c 1 2 3a 4 1 2 3 4 5
1 3 4 2 1
5 1
f 2
e g d b 2
Let A = 3
c f A+I= 1 a
5 4
g e h 3 1
h 5
d 1 b
4 c 1 f
5 g e h+1

 In (A+I) matrix there is a self loop at node 5. Now we can obtain (A+I)* after
removing the self loop at node 5 by applying loop reduction step.
 i.e. To remove self loop at node 5 multiply loop term h* with all row elements of row 5.
1 2 3 4 5
1 1 a
2 1
(A+I)* = 3 d 1 b
4 c 1 f
5 h*g h*e 1

(A+I)2* = (A+I)* (A+I)*

1 2 3 4 2 3 1 2 3 4
1 4 5
1 1 5 a 1 1 ad
5 a ab
2 1 1 1 a 2 1
= 3 d 1 b 2 1
= 3 d+bc 1 b bf
4 c 1 f x 3 d 1 b c+fh*g fh*e 1 f
h*g h*e 4
5 1 4 c 1 f h*g+h*ed h*e h*eb 1
5
5
h*g h*e 1
1 2 3 4 5
(A+I)3* = (A+I)2* (A+I)*
1 2 = 3 5 1 2 3
4
1 3
ad a ab 1
4
1
1 5 2
2
d+bc 1 b bf x 3
c+fh*g fh*e 1 f Page 37
h*g+h*ed h*e h*eb 1
www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
4 4 5 1 4 1 ad+abc a ab abf
5 2 1 a 1
3 1 5 d+bc+ 1+ b bf
= d 1 b bfh*g bfh*
c 1 f e
 No new loops were found for the second power1matrix
h*g h*e c+fh*g+ 1+ f
fh*ed fh*e fh*e
b
h*g+h*ed 1+
+h*e(d+bc) h*e h*eb h*e

Page 38

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
 But the third power matrix has a loop term bfh*e at node 3. So all other
entries in that row are multiplied by (bfh*e)*. Similarly there is a loop term
(fh*eb) at node 4.
 So all other entries in that row are multiplied by (fh*eb)*. Also a loop
term (h*ebf)* at node 5.
 So all other entries in the fifth row is multiplied by (h*ebf)*
(iv) Explain about Partitioning Algorithm in detail?
Partitioning Algorithm:
 It is an algorithm which is used to transform the graphs with loops into loop free
graphs.
 There are certain points to remember here. They are
1. A graph is loop free at the top level.
2. Many graphs with loops are easy to analyze, if you know where to break the
loops.
3. This algorithm is used to develop a tool which can identify the loops.
 The partition algorithm
represents. (A+I)n #
(A+I)nT
Example:
 Consider the following flowgraph and its graph matrix (A + I).

1 1 2 3
4 5 6 7 8
1 1 1
2 7 2 1 1 1
8 3 1 1
3 A+I 4
= 1 1 1
5 5 1 1
4 6 1
7 1 1 1
6 8 1 1

 The transitive closure matrix (A+I)n can be obtained by using the

following steps. Step:1: Mark all diagonal entries by 1
Step:2: The flow from node 1 to node 6 is 1-2-7-2-3-4-
5-3-4-6 So mark nodes 1,2,3,4,5,6,7 by 1 in
the first row
Step:3: The flow from node 2 to node 6 is 2-7-2-3-4-5-
3-4-6 So mark nodes 2,3,4,5,6 by 1 in the
second row.
Step:4: The flow from node 3 to node 6 is 3-4-5-3-4-6.
So mark nodes 3,4,5,6 by 1 in the third
row Step:5: The flow from node 4 to node 6 is 4-
5-3-4-6.
So mark nodes 3,4,5,6 by 1 in the fourth row
. Step:6: The flow from node 5 to node 6 is 5-
3-4-6. So mark nodes 3,4,5,6 by 1 in
Page 39

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
the fifth row.
Step:7: The flow from node 6 is only 6. So mark node 6 by 1 in the sixth
row. Step:8: The flow from node 7 to node 6 is 7-2-3-4-5-3-4-6
So mark nodes 2,3,4,5,6,7 by 1 in the seventh row
. Step:9: The flow from node 8 to node 6 is 8-3-4-
5-3-4-6 So mark nodes 3,4,5,6,8 by 1 in
the eighth row

Page 40

www.Jntufastupdates.c
om
 Software Testing Methodologies Unit V
 Therefore the transitive closure matrix is.
1 2 3 4 5 6 7 8
1
1 1 1 1 1 1 1
2
1 1 1 1 1 1
3 1 1 1 1
(A+I)n 4
= 1 1 1 1
5 1 1 1 1
6 1
7 1 1 1 1 1 1
8 1 1 1 1 1

 The transpose of (A+I) is. n

1 2 3 4 5 6 7 8
1 1
2 1 1 1
3 1 1 1 1 1 1 1
(A+I)nT = 4 1 1 1 1 1 1 1
5 1 1 1 1 1 1 1
6 1 1 1 1 1 1 1 1
7 1 1 1
8 1

 The intersection of transitive closure matrix (A+I)n and transpose matrix (A+I)nT
is given by, identifying similar rows and column entries from (A+I) n and (A+I)nT
1 2 3 4 5 6 7 8
1 1
2 1 1
3 1 1 1
4 1 1 1
(A+I)n#(A+I)nT=5 1 1 1
6 1
1 1
7
1
8

 From the above matrix, by comparing a row/column with other

rows/columns, the equivalent nodes to be grouped.
 After grouping
Let A=[1] B=[2,7] C=[3,4,5] D=[6] E=[8]
 The graph and graph matrix representation to the above values is given by
FlowGraph .
1
A
Graph Matrix

A B C D E 2,7
ABCDE B 1 1
8 1 1
E
1 1
3,4,5 1
C
1 1

6
D

Page 41

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
(v) Explain about Breaking Loops And Applications:
 Consider the matrix format of a flowgraph.
 If there are any entries on the principal diagonal, then break the loop for that link.
 Here we use successive powers of the matrix.
 Another way to break the loop is applying the node reduction algorithm.
 Here we break the loop or we remove the self loop at any node is, by
multiplying loop term with all other entries in that corresponding row.
(vi) Explain about Some matrix properties?
 To interchange the node names in the flowgraph, we must interchange both the
corresponding rows and the corresponding columns of the node names in the
graph matrix.
 Consider the following flowgraph and its Graph matrix.
d 1 2 3 4 5
a b c
1 3 4 2 1 a
f 2
e g d b
3
5 4 c f
5 g e h
h

 Interchange rows 3 and 4 to the above graph matrix.

1 2 3 4 5
1 a
2
3 c f
4 d b
5 g e h
 Interchange columns 3 and 4 to the above graph matrix.
1 2 3 4 5
1 a
2
3 c f
4 d b
5 g e h

 The flowgraph to the above graph matrix is given by.

d
a b c
1 4 3 2
f
e g
5
h
 By comparing the above flowgraph with the given flowgraph, it is proved that
nodes 3,4 are interchanged

Page 42

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
(7) Building Tools:
Explain about building tools of graph matrices?
i. Matrix Representation in software:
 A graph is an abstract representation of the software structure.
 Theoretically speaking, graphs are the simple structures but when used in
theorem proving we have to apply graph matrices.
 It consists of
a) Overview:
 We prove theorems and develop graph algorithms by using graph
matrices. When we want to process graphs in a computer we represent
them as linked lists.
b) Node degree and graph density:
 Each intermediate node may have any number of inner links and outer links.
 The inner links of a node represents the in degree of the node.
 Similarly the outer links of a node represents the out degree of a node.
 The sum of in degree and out degree of a particular node is the degree of that
node.
 The average degree of a node for a graph is between 3 and 4.
 The degree of a simple branch and simple junction is 3.
 The degree of a loop in a graph is 4.
 Any graph with average degree of 5 or 6 is said to be a very busy flowgraph.
c) What is wrong with arrays:
 We can represent the matrix as a two-dimensional array for small graphs
with simple weights, but this is not convenient for larger graphs because
(i) Space:
 Matrix representation requires a large storage space.
 Hence a linked list representation is used which requires less storage space.
(ii) Weights:
 An additional weight matrix is required for complicated link weights.
(iii) Variable-Length Weights:
 The link weights in a flow graphs are represented in a two dimensional
string array (matrix format), in which most of entries are null.
(iv) Processing time:
 Since many entries of the graph matrices are null, the time taken to
process such entries are more.
d) Linked-list Representation:
 Consider following the flowgraph.

d
a b c
1 3 4 2
f
e g
5
h

Page 43

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
 The linked list for the above flowgraph is

Page 44

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
1,3;a
2,exit 3,2;d
3,4;b
4,2;c
4,5;f
5,2;g
5,3;e
5,5;h
 List entries are usually placed in lexicographic (dictionary) order.
 The link weight expressions are stored in a string array to which link
names act as pointers.
 If the link weights are values then, they are stored in an array of fixed length.
List Entry Content
1 node 1,3;a
2 node 2,exit
3 node 3,2;d
,4;b
4 node 4,2;c
,5;f
5 node 5,2;g
,3;e
,5;h
 The node names appear only once, at the first link entry. A node name i.e
starting node is used for the list entry.
 And there are back pointers for the inlinks. So we get
List Entry Content List Entry Content
1 node 4 node 4,2;c
1,3;a ,5;f
2 node 3,
2,exit 5 node 5,2;g
3, ,3;e
4, ,5;h
5, 4,
3 node 5,
3,2;d
,4;
b 1,
5,
 It is important to keep the lists sorted in lexicographic order with the
following priorities: node names or pointer outlink names, inlink names.
2. Matrix Operations:
a) Parallel Reduction:
 Parallel links after sorting are adjacent entries with the same pair of node
names. Ex:
y
node 17,21;x
21
x 17 z 44 ,44;y
w Page 45

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
,44;z
,44;w
 We have three parallel links from node 17 to 44. So

Page 46

www.Jntufastupdates.c
om
 Software Testing Methodologies Unit V
Node 17,21;x
,44;y(where y=y+z+w)
b)Loop Reduction:
 The loop reduction step is used to remove the loop. Here self link represents the
loop.
 For removing a loop, the loop term is multiplied with all the outer links of
the node at which the loop presents. Consider the following example.
d
a b c List Entry Content Before Content After
1 3 4 2
5 node node 5,2;h*g
f 5,2;g ,3;h*e
e g
,3;
5 e 4,
h ,5;
h 4,
c) Cross term reduction: 5,
 Select a node for
reduction.

 The cross term reduction represents that we combine every inlink to the
node with every outlink from that node after removing that node.
 The links created by node removal are stored in a separate list which is then
sorted and thereafter merged into the master list.
d) Addition, Multiplication and other operations:
 Here addition of two matrices is simple. Multiplication is more complicated.
 Transposition is done by reversing the pointer directions, resulting in a list
that is not correctly sorted. Sorting that list provides the transpose. All other
matrix operations can be easily implemented by sorting, merging, and
combining parallels.
List Entry Content Before Content After
d
2 node 2,exit b node 2,exit
1 a 3 4 c 2
3, 3,
f 4, 4,
e g 5, 5,
5 3 node 3,2;d node 3,2;d
h ,4;b ,2;bc
,5;b
1, f 1,
5, 5,
4 node 4,2;c
,5;
f 3,
5 node node
5,2;h*g 5,2;h*g
,3;h* ,3;h*e
e 4,
3. Node Reduction
Optimization:
 The optimum order for node reduction is to do lowest-degree nodes first. The
Page 47

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
idea is to get the lists as short as possible as quickly as possible. Nodes of
degree 3 reduce the total link count by one link when removed. A degree-4
node keeps the link count the same, and all higher-degree nodes increase the
link count.
 For large graphs with 500 or more nodes and an average degree of 6 or 7,
the difference between not optimizing the node-reduction order and
optimizing it was about 50: 1 in processing time.
 Types of Transition Bugs
 1. Unspecified Transitions
 These occur when a possible transition between two states is not
defined.
 If an input is received in a given state but no transition is defined for that
input, the system may behave unpredictably or inefficiently.
 Example: Suppose state A receives input X, but there is no rule telling the
system what to do—this is an unspecified transition bug.
 Prevention:
 Every state-input combination must have a defined transition to avoid bugs.
 Implement proper methods or conditions to block or handle invalid inputs
in certain states.


 2. Contradictory Transitions
 These happen when transitions are defined, but they contradict the
intended logic or structure of the system.
 It can occur if a programmer mistakenly defines a transition that shouldn't
happen, like specifying a jump from State A to State C even though it
logically cannot happen.
 Example: A single-bit error in state representation can lead to doubling the
number of states, making some transitions illogical or contradictory.
 Impact:
 Leads to logical inconsistencies, unpredictable behavior, and system
failures.


 ✅ Best Practices to Avoid Transition Bugs

 Ensure complete transition coverage (every input for every state has a
defined outcome).
 Implement guard conditions or error handling to block invalid transitions.
 Conduct state diagram validation and logic reviews to avoid
contradictions.
 Use automated tools to verify finite state machines for missing or invalid
transitions.


 Would you like a diagram of a state machine showing examples of

unspecified and contradictory transitions?
 You said:
 example with diagram
 ChatGPT said:
Page 48

www.Jntufastupdates.c
om
Software Testing Methodologies Unit V
 Certainly! Let's delve into examples of Unspecified and Contradictory
Transitions in state machine diagrams, accompanied by visual
representations.


 1. Unspecified Transition Bug

 Scenario:
 In a state machine, if an input is received in a state but no transition is
defined for that input, the system may enter an undefined state or behave
unpredictably.
 Example:
 Consider a system with the following states and transitions:
 States: A, B, C
 Inputs: X, Y
 Current  Input  Input
State X Y
 A  B  A
 B  C  B
 C  ?  C
 In this table, for State C, the transition for Input X is unspecified (denoted by
"?"). This oversight can lead to unpredictable behavior when Input X is
received in State C.
 Diagram:
 plaintext
 CopyEdit
 +---+ X +---+ X +---+
 | A | --------> | B | --------> | C |
 +---+ +---+ +---+
 | | |
 |Y |Y |Y
 v v v
 +---+ +---+ +---+
 |A| |B| |C|
 +---+ +---+ +---+
 In the diagram, the transition from State C on Input X is missing, representing
an unspecified transition bug.


 2. Contradictory Transition Bug

 Scenario:
 Contradictory transitions occur when multiple transitions are defined for the
same input in a given state, leading to ambiguity.
 Example:
 Consider a system with the following states and transitions:
 States: A, B, C
 Inputs: X, Y

Page 49

www.Jntufastupdates.c
om
 Software Testing Methodologies Unit V
 Current  Input  Input
State X Y
 A  B  A
 B  C  B
 C  A, B  C
 In this table, for State C, Input X leads to both State A and State B, which is
contradictory and ambiguous.
 Diagram:
 plaintext
 CopyEdit
 +---+ X +---+ X +---+
 | A | --------> | B | --------> | C |
 +---+ +---+ +---+
 | | |
 |Y |Y |Y
 v v v
 +---+ +---+ +---+
 |A| |B| | A/B |
 +---+ +---+ +---+
 In the diagram, the transition from State C on Input X leads to both State A
and State B, indicating a contradictory transition bug.


 Conclusion
 Unspecified and contradictory transitions can lead to unpredictable or
erroneous behavior in a system. It's crucial to ensure that:
 Every state-input combination has a defined transition (no unspecified
transitions).
 Each state-input combination leads to a single, unambiguous next state (no
contradictory transitions).
 By carefully designing state machines and thoroughly reviewing state
transition tables, such issues can be avoided, leading to more reliable and
predictable system behavior.
Unreachable States
 If transitions are not defined for all inputs in all states, some states (like 6, 7)
might never be entered.
 For example, if no ERROR from 5 goes to 6, and there's no OK path either, 6 may
be unreachable.
❌ 2. Dead States
 A state is dead if no transition exists from it. For instance, state [6] may be a
dead state if there’s no valid transition from it back to any earlier state or it only
leads to OUT.
⚠️3. Output Errors
 If a transition is correct but the action/output (e.g., "REWRITE") is incorrectly
implemented or missed, that's an output error.
 Example: In state 2, an ERROR leads to REWRITE, ERASE — but if only REWRITE
happens due to a bug, it’s an output error.
🧩 4. Encoding Bugs
Page 50

www.Jntufastupdates.c
om
 Software Testing Methodologies Unit V
 Suppose states are coded as 000, 001, ..., 111 in binary (for 0 to 7).
 If the programmer uses incorrect binary values or mislabels transitions (e.g.,
using state 010 for both 2 and 4), transitions may go to wrong states.
 Or if the output code (like REWRITE) is mismatched due to encoding
misunderstanding, this leads to silent failure.

Impact of Bugs in State Graphs

1. Wrong number of states – states added/removed unintentionally.
2. Wrong transitions – incorrect links between states.
3. Wrong output – incorrect or missing action for a transition.
4. Wrongly equivalent states – distinct behaviors treated as the same.
5. Duplicate states – same behavior split across multiple states.
6. Dead states – once entered, system can’t continue.
7. Unreachable states – no path leads to them.
(ii) Principles of State Testing
 Focus on states and transitions, not just outputs.
 Use input sequences to trigger transitions and check expected state/output.
 Testing targets input → transition → output sequences.
(iii) Limitations & Extensions
 Coverage ≠ completeness.
 Chow's method: test sequences of increasing length (0-switch, 1-switch…).
 FSMs are good for early bug detection but may miss complex combinations.
(iv–v) Modeling, Data & Tools
 Suitable for hardware + software systems.
 Needs effort: data gathering, meetings, and special design tools.
(vi) Testability & FSM Size
 FSMs grow exponentially; most combinations are faulty.
 Use flags/switches to guide paths and reduce complexity.
 Eliminate unachievable paths to focus on relevant behavior.

📘 FSM Example Diagram

Let’s visualize a simple finite state machine (FSM) and highlight key problems.
FSM:
rust
CopyEdit
[START] --ok--> [1] --ok--> [2] --error--> [3]
\--error--> [4] (dead state)
[3] --ok--> [5] --ok--> [6] --ok--> [END]
(missing error path)
[7] = unreachable

🔍 Explanation of FSM Issues in Diagram:

Issue Explanation
❌ Unreachable State [7] is not connected to any other — can never be
State reached.
State [4] has no outgoing transition — system halts if
⚰️Dead State
entered.
Page 51

www.Jntufastupdates.c
om
 Software Testing Methodologies Unit V
Issue Explanation
⚠️Missing From [5], an error input isn’t handled — what happens if it
Transition occurs?
❗ Output Bug Suppose [2] --error--> [3] should trigger REWRITE, but due to
Example a bug it does ERASE — output bug.

Page 52

www.Jntufastupdates.c
om