1, Figure 6.1) from a run of our model program.
It is also possible to generate runs from an FSM. This is how we do offline test
generation.
Each FSM describes every run that can be obtained by traversing a path around
the nodes and links in its graph. Here is an informal description of the algorithm for
generating one run: Begin in the initial state. In a state that has transitions to next
states, choose any one. For example, the middle node in Figure 6.1 has two outgoing
transitions, so two choices are available. If we reach a state with no outgoing transitions,
the run finishes in that state. Or, if the state has been designated an accepting
state, we may choose to finish the run in that state. In this example, we have have
not designated any accepting states, so every state is considered an accepting state;
the run may finish in any state.
We often describe this process in terms of actions, rather than transitions. An
action is enabled in a state if it is allowed to begin in that state; otherwise, it is
Systems with Finite Models 97
disabled in that state. Every transition out of a state is labeled with one of the
actions that is enabled in that state. For example, in the middle node in Figure 6.1,
two actions are enabled: SortByFirst and ShowText. The heart of the traversal
algorithm can be expressed: in each state, choose an enabled action and execute it.
Pages:
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147