UNIT-4

STATES, STATE GRAPHS, AND TRANSITION TESTING

I. The behavior of the system is represented in graphical form which is known as State graph.
II. State graph is used for functional testing of the system to identify different bus
 State bus
 Transition bugs
Elements:
 States
 Inputs
 Transitions
 Outputs

State Graphs:
 A state is defined as: “A combination of circumstances or attributes belonging for the time
being to a person or thing.”
 For example, a moving automobile whose engine is running can have the following states with
respect to its transmission.
 Reverse gear
 Neutral gear
 First gear
 Second gear
 Third gear
 Fourth gear
State graph - Example
 For example, a program that detects the character sequence “ZCZC” can be in the
following states.
 Neither ZCZC nor any part of it has been detected.
 Z has been detected.
 ZC has been detected.
 ZCZ has been detected.

Department of CSE Page 1 of 7

  ZCZC has been detected.

States are represented by Nodes. State are numbered or may identified by words or
whatever else is convenient.
A finite state machine is an abstract device that can be 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 kinds of inputs:
1. Z
2. C
3. Any character other than Z or C, which we’ll denote by A.
The state graph of Figure 9.1 can be interpreted as follows:
1. If the system is in the “NONE” state, any input other than a Z will keep it in that state.
2. If a Z is received, the system transitions to the “Z” state.
3. IF the system is in the “Z” state and a Z is received, it will remain in the “Z” state. If a C is
received, it will go back to the “ZC” state; if any other character is received, it will go back to the
“NONE” state because the sequence has been broken.
4. A Z received in the “ZC” state progresses to the “ZCZ” state, but any other character breaks the
sequence and causes a return to the “NONE” state.
5. A C received in the “ZCZ” state completes the sequence and the system enters the “ZCZC” state.
A Z breaks the sequence and causes a transition back to the “Z” state; any other character causes a
return to the “NONE” state.
6. The system stays in the “ZCZC” state no matter what is received.
Inputs and Transitions:
Whenever an input is applied on any state, As a result of those inputs, the state changes, or is
said to have made a Transition.
Transitions are denoted by links that join the states.
The input that causes the transition are marked on the link; that is, the inputs are link weights.
There is one out link from every state for every input.
 If several inputs in a state cause a transition to the same subsequent state, instead of drawing a
bunch of parallel links we can abbreviate the notation by listing the several inputs as in:
“input1, input2, input3………”.
Department of CSE Page 2 of 7
 Finite State Machine
A finite state machine is an abstract device that can be represented by a state graph having a
finite number of states and a finite number of transitions between states.
 Outputs:
An output can be associated with any link.
 Out puts are denoted by letters or words and are separated from inputs by a slash as
follows: “input/output”.
 If every input associated with a transition causes the same output, then denoted it as:
o “input1, input2, input3…............../output”
State
Tables

It’s more convenient to represent the state graph as a table (the state table or state
transition table) that specifies the states, the inputs, the transitions and the
outputs.
 The following conventions are used:
 Each row of the table corresponds to a state.
 Each column corresponds to an input condition.
 The box at the intersection of a row and a column specifies the next state (the
transition) and the output, if any.
State Table-Example

Department of CSE Page 3 of 7

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.

 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 tape one block and rewrite the block (output =REWRITE) i.e.
enter into state 2.

 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 enters into state 3 & then state
1. At state 3 if any error is detected then it enters 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
Time Versus Sequence

A transition might take microseconds or centuries;

Department of CSE Page 4 of 7
 A system could be in one state for milliseconds and another for years- the state graph would
be the same because it has no notion of time.
Good State Graphs and Bad
What constitutes a good or a bad state graph is to some extent biased by the kinds of state
graphs that are likely to be used in a software test design context.

In order to judge whether state graph is good one, we can use following principles:

1. The total number of states in a given state graph is equal to product of the possibilities of
factors that make up the states.

2. For every state and input, there is a unique transition to exactly one state and may be the
same state itself

3. For every transition there is one specific output action.

4. For every state there is a sequence of inputs that will drive the system back to the same state

Department of CSE Page 5 of 7

Bugs in State Graphs or State Bugs:
When testing an implementation against a State Graph, one shall study the following typical
bugs (incorrect sequences of events, transitions, or actions):
 Unspecified transition (nothing happens with an event)
 Incorrect transition (the resultant state is incorrect)
 Unspecified or incorrect action (wrong things happen as a result of a transition)
 Extra, unspecified or corrupt state
 Unreachable State (A state that no input sequence can reach
 Dead State (A state that once entered cannot be exited)
 Sneak path (an event is accepted when it should not be)

Department of CSE Page 6 of 7

 1) Number of States:
The number of states in a state graph is the number of states we choose to recognize or model. The state
is recorded as a combination of values of variables that appear in the database. Failure to account for all
the states is one of the most common types of bugs that can be modeled using a state-graph.

2)Equivalent States
Two states are Equivalent if every sequence of inputs starting from one state reaching to same
outputs state when started from the other state. This notion can also be extended to set of
states.

Merging of Equivalent States

Department of CSE Page 7 of 7

Transition Bugs-
unspecified and contradictory Transitions
Every input-state combination must have a specified transition.
If the transition is impossible, then there must be a mechanism that prevents the input from
reaching that state.
Exactly one transition must be specified for every combination of input and state. A program
can’t have contradictions or ambiguities in transitions.
Unreachable States
An unreachable state is like unreachable
code.
This is usually because the state became unreachable as a result of incorrect transition.
There are two possibilities for unreachable states:
o There is a bug; that is some transitions are missing.
o The transitions are there, but you don’t know about it.

Dead States
A dead state is a state that once entered cannot be
left. This is not necessarily a bug but it is suspicious.

Output Errors

The states, transitions, and the inputs could be correct, there could be no dead or unreachable
states, but the output for the transition could be incorrect.
Output actions must be verified independently of states and transitions

Test Design Strategies for State Graph based Testing

Test cases derived from State Graph are sequence of input events.
 All states coverage is achieved when each state of the State Graph is exercised at least
once during testing.
 All-actions coverage: Each action is executed at least once
 All-transitions coverage: All-transitions coverage is achieved when the test executes
every transition in the model at least once. This automatically entails also all states
coverage.

Starting point of state testing

Define a set of covering input sequences that starting from the initial state.
For each step in each input sequence, define the expected next state, the expected transition,
and the expected output code.
A set of tests, then, consists of three sets of sequences:
o Input sequences
o Corresponding transitions or next-state names
o Output sequences

Department of CSE Page 8 of 7

State Transition Testing:

State transition testing examines how a software system changes from one state to another in response to
events. States are various conditions or modes that a system can be in.
Specific events trigger transitions and depict the movements between these states.
In this approach, we analyze how software behaves under different scenarios, considering the events that
cause transitions and the actions that follow. State transition testing is beneficial for systems with a clear
sequence of states and events. This is because it systematically examines how the software responds to
different scenarios, ensuring proper behaviour during transitions between states triggered by specific events.
Moreover, this approach enhances test coverage and aids in identifying potential defects in systems where
state changes follow a well-defined sequence.
For example, let’s say we have a traffic light system that changes signals based on time of day, traffic
volume, and pedestrian presence. State transition testing would help ensure the system responds correctly to
different combinations of these factors.

State Transition Diagrams: A Visual Representation

We visualize the state transition testing using state transition diagrams. These diagrams provide a graphical
representation of a system’s states, transitions, events, and actions.
State transition diagrams consist of states represented by rectangles, transitions shown as arrows between
states, events triggering transitions, and actions associated with transitions:

Circles denote the start and end states.

Such diagrams give us a clear and structured view of how our software behaves in response to different
inputs. So, they help us identify potential defects, verify correct state transitions, and ensure that the software
performs as intended.
The state transition diagrams provide the basis for developing test cases and examining the behaviour of our
software.

Applying State Transition Testing

To apply state transition testing effectively, we follow these steps:

1. Identifying states and events: We begin by understanding the different states of the system and the
events that trigger state transitions. This involves analyzing system requirements and specifications
2. Creating state transition diagrams: We develop state transition diagrams to visualize the states,
transitions, events, and actions. These diagrams provide a clear overview of the software’s behavior
Department of CSE Page 9 of 7
 3. Deriving test cases: We derive test cases from the state transition diagrams that cover all possible
state transitions and event combinations. For each test case, we specify the initial state, event
trigger, and expected outcome
4. Executing tests: We execute the derived test cases on the software and observe how the system
transitions between states. This step determines whether the expected actions are performed
accurately
5. Analyzing results: In the final step, we evaluate the test results to ensure the software behaves as
intended. Finally, we document and address any discrepancies or deviations from expected behavior

4.1. Example

Let’s explore a real-world example to understand state transition testing better. We’ll explore how state
transition testing can be applied to an Automated Teller Machine (ATM) system.
The ATM system undergoes various states and transitions based on user interactions:

We first identify states within the ATM system, such as “Card Inserted,” “PIN Entered,” and” Transaction
Selection. After the identification of states, we’ll define events that trigger transitions between these states.

Department of CSE Page 10 of

7
We depict transitions through a diagram, illustrating the progression from one state to another when an event
occurs. For example, we move from “Card Inserted” to “PIN Entered” upon encountering the “Insert PIN”
event.
In all these transactions, we incorporate conditions that influence these transitions, such as the condition “If
the PIN is valid” for the shift from “PIN Entered” to “Transaction Selection.”

4.2. Test Cases

We formulate test cases based on the state transition diagram, covering scenarios like card insertion
without subsequent PIN entry, entry of an incorrect PIN, selection of distinct transaction types, rejection of a
transaction, and successful transaction completion.
Moreover, we test the ATM system using pre-planned scenarios to make sure that the user interactions lead
to seamless state transitions. After the tests are done, we analyze the results to confirm that the actual state
transitions match the expected ones, as shown in the state transition diagram. Finally, we document and
report any identified disparities and potential defects in the system.

5. Advantages

Advantages

We use state transition testing to explore software behaviour across diverse scenarios. That way, we ensure
systematic coverage of various conditions by mapping out states, transitions, and events. Therefore, this
approach allows us to identify critical pathways involving state transitions and events.
State transition diagrams offer a clear and easy-to-understand depiction of complex software
actions. This clarity enhances understanding and fosters effective communication among our testing team
and stakeholders.
Additionally, our test case development process benefits from state transition diagrams, guiding us to
identify relevant test scenarios and ensuring systematic coverage of these scenarios. This leads to the creation
of comprehensive and well-structured test cases.

Department of CSE Page 11 of

7