Page 263 -
P. 263

6.3 Syntactic Analvsis   251


                              A  formal language L  is  a subset of  T+ u{h}, constituted by  strings obeying
                              certain rules.

                            2, N is a set of  class symbols, also called non-terminal symbols, i.e., symbols that
                              denote  classes  of  elements  of  T.  For  instance,  when  describing  natural
                              languages, we would use non-terminal symbols to denote the classes of  words
                              that are "nouns", "adjectives", "verbs", etc.
                              The  sets  T and  N  are  disjointed and  their  union,  V = T u N , constitutes the
                              language vocabulary.

                            3.  P is a set of  syntactic rules, known  as production  rules, used  to generate the
                              strings. Each rule is represented as:

                              a  ~  p  ,  with   ~EV+,~EV~U{X}.                           (6-6b)

                              The production rule  a I+   , read  "a produces ,8 ", means that any occurrence
                              of a in a string can be substituted by ,8.

                            4. S is a special parent  class symbol, also called starting symbol, used to start the
                              generation of any string with the rules of P.

                              Let  us  apply  the  above  definitions  to  a  waveform recognition  example,  by
                            considering signal  waveform descriptions where  a  waveform is  built  with  only
                            three primitives: horizontal segments, h; upward segments, u; downward segments,
                            d. Hence, the pattern alphabet is, in this case, T= {h, u, d}.
                              We now consider the following classes of strings of T:

                               Pt  : upward peak;
                               P- : downward peak;
                              H  : horizontal plateau.

                              Hence. N = {P*, P-. H].
                              We can now define a production rule for an upward peak as:




                              Another production rule for the same class could be:




                               As this last rule is a recursive rule, we are in fact describing upward peaks as an
                             arbitrary number of u primitives followed by the same number of d primitives. We
                             can write the previous rules (6-7a) and (6-7b) compactly as:
   258   259   260   261   262   263   264   265   266   267   268