Adapting Grammar Inference Techniques to Mine State Machines - Mining Software Specifications: Methodologies and Applications - page 61

FIGURE 3.1: Model of a simple text editor.

state machines. Active techniques have been developed to guide the collection
of traces. Constraints can be added to summarize large numbers of traces,
further enhancing the accuracy and eciency of inference techniques.
This chapter will describe the conventional reverse-engineering approach
and its problems in more detail in Section 3.2. Section 3.3 will describe the
advances that are key to addressing these individual problems. Where appro-
priate it will contain algorithms that show how these advances can be (and
have been) combined to produce more powerful state machine mining tech-
niques. Section 3.4 shows how temporal constraints that are supplied by the
user can be integrated into the inference process as well. Finally, Section 3.5
offers some conclusions, and outlines some areas for future work.

3.2 The Conventional Reverse-Engineering Approach

and Its Problems
We begin this section by providing a short introduction to state machines,
(partial) labeled transition systems, and their languages. This is followed by
an introduction to the conventional reverse-engineering techniques such as the
k-tails algorithm. The section is concluded by a more detailed treatment of
the problems mentioned in the introduction that tend to hamper the practical
application of such reverse-engineering techniques.

3.2.1 State Machines and Their Languages
The basic structure of a state machine can be visualized diagrammat-
ically, as a Labelled Transition System (LTS). An LTS is a quadruple
A = (Q; ;;q 0 ), where Q is a nite set of states, is a nite alphabet,
: Q ! Q is a partial functions and q 0 2 Q. An example of an LTS is
shown in Figure 3.1, which shows the state-based behavior of a simple, fic-
tional text editor. We shall use this example later on to illustrate some of the
basic state machine inference concepts.