Page 272 -

260 6 Structural Pattern Recognition

instance, in Figure 6.11 the second and fourth events do not satisfy such
conditions, although they parse as "accelerations". We will see in the following
how to take into account primitive attributes.

Figure 6.12. State-diagram of a finite-state automaton for the recognition of FHR
accelerations.

6.3.5 Attributed Grammars

Until now, we have only considered grammars for string descriptions alone.
However, as seen in the previous example of FHR acceleration detection, the
qualitative information provided by a string may not be enough for correct
recognition. In the mentioned example, if we want to detect "true" accelerations,
we will have to appropriately use the information on the length and slope of the
segments. In other applications other information may have to be used, such as
angle orientation of line segments, textural information or surface orientation. For
this purpose, we will have to deal with attributed strings and use an attributed
grammar, with the same definition as before, plus the addition of semantic rules. A
pair "syntactic rule - semantic rule" for a regular grammar is:

where a(@ is the attribute vector of the non-terminal a computed in terms of the
attribute vector of the terminal b.
An attribute vector can be interpreted as a feature vector. When parsing a string
with attributed grammars, one may assume that the production rules for each
symbol make its attribute dependent either on the left or on the right side of the
productions. For instance, in top-down parsing, attribute values for each symbol
are inherited from each right side symbol. We exemplify this for the first
production rule of the FHR acceleration rules (6-12b):