Page 264 -
P. 264
252 6 Structural Pattern Recognition
The symbol I denotes an exclusive "or" choice and the parentheses allow a kind
of factorisation, meaning that P+ can be substituted with u P+d or with uhd,
which is in fact ud.
Consider now that our waveform grammar has the following set of productions:
The starting symbol S stands for "any waveform obtainable with the rules of P.
The set P determines a language L(G) (or simply L) of waveforms, which is a
subset of all possible waveforms of T+ u {I) . Consider the waveform of Figure
6.7a, represented by the pattern string x = hhuuddh. Is it an element of L
(describable by P)? In order to answer this question, we have to see if it is possible
to generate x using the rules of P starting from S:
We have indeed been able to generate x with the rules of P, or, in the jargon of
formal language theory, we were able to parse x.
Figure 6.7. A signal wave (a) represented by the string x = hhuuddh and its top-
down parsing tree (b).
The chain of rules (6-7e) generating x is called a derivation of x. The
application of rules for obtaining this derivation is called top-down parsing, since
we started from the initial symbol S and went down until the terminal symbols, as
shown in the parsing tree of Figure 6.7b. It is also possible to start from the string
applying the rules in reverse order as a bottom-up parsing chain: