The intersection of Finite State Automata and Definite Clause Grammars

The intersection of Finite State Automata and Definite Clause Grammars Gertjan van Noord Vakgroep Alfa-informatica & BCN Rijksuniversiteit Groningen vannoord@let, rug. nl Abstract Bernard Lang defines parsing as ~ cal- culation of the intersection of a FSA (the input) and a CFG. Viewing the input for parsing as a FSA rather than as a string combines well with some approaches in speech understanding systems, in which parsing takes a word lattice as input (rather than a word string). Furthermore, certain techniques for robust parsing can be modelled as finite state transducers. In this paper we investigate how we can generalize this approach for unification grammars. In particular we will concen- trate on how we might the calculation of the intersection of a FSA and a DCG. It is shown that existing parsing algorithms can be easily extended for FSA inputs. However, we also show that the termi- nation properties change drastically: we show that it is undecidable whether the in- tersection of a FSA and a DCG is empty (even if the DCG is off-line parsable). Furthermore we discuss approaches to cope with the problem. 1 Introduction In this paper we are concerned with the syntactic analysis phase of a natural language understanding system. Ordinarily, the input of such a system is a sequence of words. However, following Bernard Lang we argue that it might be fruitful to take the input more generally as a finite state automaton (FSA) to model cases in which we are uncertain about the actual input. Parsing uncertain input might be nec- essary in case of ill-formed textual input, or in case of speech input. For example, if a natural language understand- ing system is interfaced with a speech recognition component, chances are that this c o ~ t is un- certain about the actual string of words that has been uttered, and thus produces a word lattice of the most promising hypotheses, rather than a single se- quence of words. FSA of course generalizes such word lattices. As another example, certain techniques to deal with ill-formed input can be characterized as finite state transducers (Lang, 1989); the composition of an input string with such a finite state transducer results in a FSA that can then be input for syntac- tic parsing. Such an approach allows for the treat- ment of missing, extraneous, interchanged or mis- used words (Teitelbaum, 1973; Saito and Tomita, 1988; Nederhof and Bertsch, 1994). Such techniques might be of use both in the case of written and spoken language input. In the latter case another possible application concerns the treat- ment of phenomena such as repairs (Carter, 1994). Note that we allow the input to be a full FSA (possibly including cycles, etc.) since some of the above-mentioned techniques indeed result in cy- cles. Whereas an ordinary word-graph always de- fines a finite language, a FSA of course can easily de- fine an infinite number of sentences. Cycles might emerge to treat unknown sequences of words, i.e. sentences with unknown parts …

Content truncated to 500 words