Page 273 -

6.3 Syntactic Analysis 261

where 1 is the length attribute and t is height of the upper segment end.
The height attribute is computed from the length and slope for the u primitives,
and may be set to zero for h and d. When a wave event is correctly parsed as an
acceleration, the values of l(ACEL) and t(ACEL) are compared with pre-specified
thresholds in order to arrive at a final decision.
Attributed strings can be used for shape categorization of object silhouettes
described by line segments, using as attributes the length and the angle of the
segments. Details on this application can be found in the works of You and Fu
(1979) and Stenstrom (1988).

6.3.6 Stochastic Grammars

Stochastic grammars provide a good example of combining structural and
statistical approaches and applying them to pattern recognition problems.
Stochastic grammars are particularly useful in situations where the same pattern
can be interpreted as belonging to more than one class, therefore having the
possibility of being generated by alternative grammars.
A stochastic grammar is a grammar whose production rules have probabilities
associated with them, such that for every symbol a; producing symbols P, there are
probabilities P, satisfying:

Pi/ "i
C,:a;.*flj (orcxi~flj), with O<f'y51, zc, =I. (6- 15)

Therefore, the probabilities associated with the same left side symbol of a
production add up to one.
The probability of x E L(G), P(x I G), is computed as:

1. If x E L(G) is unambiguous and has a derivation with k rules, each with
probability P,, then:

2. If x E L(G) is ambiguous and has I different derivations with probabilities
P,(x(G), then: