Page 270 -

258 6 Structural Pattern Recognition

State

Figure 6.10. Finite-state automaton represented by its state-diagram, with
corresponding state-transition table. The automaton recognizes waveform peaks
without horizontal plateaus.

Figure 6.10 shows the state-diagram corresponding to this finite-state
automaton, together with the state-transition table, which is a convenient way of
representing the mapping 6.
Assuming that the symbols of T represent the signal primitives mentioned
already in section 6.3.1, it is clear that this finite-state automaton recognizes any
positive or negative peaks that do not include any horizontal plateaus.
A string is said to be accepted by M if starting with the initial state we can use
the successive string symbols to progress in the state-diagram until a final state.
The set of all strings accepted by M, denoted A(M), is formally defined as:

For any regular grammar G = {T, N, P, S), it can be proved that there is a finite-
state automaton M such that A(M)= L(G) and vice-versa. The finite-state automaton
M uses the set of terminals T, and is implemented as follows:

- Q=Nu(A};
- qo = s;
- A production a H a/5 corresponds to 8 (a, a)=P ;
- A production a H a corresponds to 6(a; a)=F ;
- If P contains the production S H 1 then F={S, A} else F=(A }

Specifying a grammar that corresponds to a finite-state machine is now an easy
task, by simply reversing the above rules.