Page 269 -
P. 269

6.3 Syntactic Analysis   257

                              Figure 6.9 represents the  block  diagram of  a syntactic recogniser, having  the
                            primitive string  as input  and  class labels together with  the  syntactic derivations
                            obtained by the parser as outputs. A language L(Gi) represents the set of all strings
                            corresponding to class wi. For the example in  the previous section the languages
                            would correspond to the sub-grammars producing the derivations for the characters
                            ,y, "R", "F" and "E".
                              Notice that, when  parsing a string, one of  the following three situations may
                            occur:

                            - The  string  belongs  to  only  one of  the  class  languages. This  is  the  desirable
                              situation.
                            - The  string  belongs  to  more  than  one  of  the  class  languages.  This  is  an
                              ambiguous "borderline" string, reminiscent of feature vectors that lie in a reject
                              region.
                            - The string does not belong to any of the class languages. This is also a reject or
                              a "don't care" situation. For instance, when parsing strings of  signal primitives,
                              we  may encounter in the tail of a parsed signal wave a sequence of primitives
                              that are not parsed, corresponding to a "don't care" situation.




                            6.3.4 Finite-State Automata

                             A broad variety of syntactic recognition tasks can be achieved with the simple G3
                             grammars referred to previously. Fortunately for these grammars the parsing task is
                             quite simple to implement, using a device known as afinite-state automaton.
                               We  define  a  finite-state  automaton  (or finite-state  machine)  as  a  quintuple
                             WT, Q, 6, 90, F):
                             - Tis a symbol set (corresponding to the set of primitives);
                             - Q is a set of states of the machine;
                             - Sis a function mapping from QxT into subsets of Q;
                             - qo~ Q is the initial machine state;
                             - F L Q is the set of final states.

                               A  finite-state automaton can  be  represented  as  a labelled digraph,  known  as
                             state-diagram, with arcs representing state transitions. Let us exemplify this with:

                               T= {h, u, d}
                               Q = (S, U+, D+, U-, D-, F) ; go = S
                               S (S, h)=S;        S (S, u)=U+;
                               8 (U+, h)=S;       S(U+, u)=U+;
                               8(D+, h)=F;        6 (D +, u)=F;
                               8 (D-, h)=S;       6(D-, u)=U-;
                               S(U-, h)=F;        S(U-, u)=U-;
   264   265   266   267   268   269   270   271   272   273   274