Page 262 -

250 6 Structural Pattern Reco~nition

relations can represent a cupboard. This method has been used in several
applications, namely in character recognition (e.g., Tai and Liu, 1990; Chen and
Lee, 1996).

Figure 6.6. A cupboard (a) and its description tree (b) using the primitives and
relations of Figure 6.5.

6.3 Syntactic Analysis

Syntactic analysis is the approach to structural pattern recognition based on the
theory of formal languages. In the literature, this approach is generally called
Syntactic Puttern Recognition. The use of grammars to describe patterns is
advantageous, given the well-developed body of knowledge in this area and the
standardized way one can apply the same approach in many different
circumstances.
The disadvantages of the syntactic approach relate to the lack of sufficient
representational capability for complex patterns, and also the difficulty in
automating inference and learning procedures, which means that in general one
first has to devise the appropriate grammar for the problem at hand.

6.3.1 String Grammars

The theory of formal languages allows us to apply structure rules to strings of
pattern primitives in a similar way as we apply grammar rules to words in a natural
language.
We proceed to define a formal string grammar as a quadruple G = (T, N, P, S):

1. T is a set of symbols, called terminal symbols, corresponding in the case of the
patterns to the set of primitives, also calledputtern alphabet.
The set of strings built with the elements of T is usually denoted p: