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:
   259   260   261   262   263   264   265   266   267   268   269