Page 277 -

6.3 Syntactic Analysis 265

Imagine now that the training set T also contained the example uhhud. In this
case, the successors of h contain h itself, therefore, the state diagram shown in
Figure 6.16a represents the corresponding automaton.

Figure 6.16. A modified finite-state diagram for FHR accelerations (a) and its
minimized version (b).

Since states q, and qh now have the same successors, they can be merged,
leading to the minimized automaton shown in Figure 6.16b. The rules for building
the initial state diagram based on successors of symbols and the rules for merging
states are easily put into algorithmic form. Once the minimized state diagram is
obtained the inferred grammar can be derived by the following inverse rules from
section 6.3.4:
- N=Q;
- S = 90;
- A H aB if S(A,a) = B with A, BE Q, a€ 7';
- AH^ if &A,a)=C€FcQ.

6.4 Structural Matching

The key idea in structural matching is to determine the similarity between an
unknown pattern and some prototype pattern by using a similarity measure
adequate for the structural representations of the patterns.

6.4.1 String Matching

String matching is based on a similarity measure between two strings x and y with
n and m symbols, respectively, and is defined in terms of the number of elementary