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: