ABSTRACT
This chapter illustrates the view of a simple grammatical description. Identifying a string of words as syntactically well-formed is a process known as recognition. Parsing, on the other hand, goes beyond recognition by associating a syntactic structure to those expressions that have been recognized. The two processes are intimately linked since both depend upon the use of the same grammatical information. Perhaps, the simplest recognition procedure imaginable would involve listing all possible sentences and then checking any test string against this list. A grammar is a description of the structures that underlie the sentences of a language. One of the simplest forms of grammatical description is expressed by a sentence frame grammar. This diagram is a graph. A graph consists of a set of nodes linked together by arcs. Such graphs are referred to as finite-state transition networks (FSTN) for reasons that will become apparent. The resulting grammar is a finite-state grammar.
