Page 268 -

256 6 Structural Pattern Recognition

The following relations exist for these four types of grammars: GO 3 G1 2
G2 3 G3. This is called the Chomsky' hierarchy, named after Noam Chomsky
whose contribution to the formal language theory was capital.
The representational power of a grammar decreases as we go from a type GO
grammar to a type G3 grammar.
Production rules of a type GI grammar can also be written:

a,aa,~a,~a,, with EN, P€Vf, aI,a2~~+u{~). (6- 10)

Therefore, a substitutes Pin the context of al and q. This justifies the context-
sensitive name given to this type of grammars (see also Exercise 6.2). For a
context-free grammar, the substitution of a by P is independent of the context in
which a appears. Since these grammars allow self-embedded productions of the
type cz H ,4,8,!3,, they can generate arbitrarily long sequences of terminals by
iteration of the same rule. Regular grammars are a special case of context-free
grammars that allow very simple representation and parsing, as will be explained
in the following section.
As we saw in the previous section, the task of assessing a pattern structural class
is equivalent to seeing whether it can be parsed by a suitable parser, which applies
the grammar's rules. Parser building for GO and GI grammars can be a very hard
task. Fortunately, structural recognition problems can often be solved using G2 and
G3 grammars, which allow a broad range of string expressiveness. For these
grammars there is a bulk of knowledge about parser building. As a matter of fact,
there are commercialised and free-ware parsers that can, in principle, be applied to
syntactic pattern recognition. The reader may also obtain information on how to
build a parser for G2 grammars in (Schalkoff, 1992).

Parser
x E L(G,)? + 4

x E L(G,)? 4 m2
X

x E L(G,)? + mc

Figure 6.9. Block diagram of a syntactic pattern classifier. L(GJ are the class
languages.