**Gertjan van Noord
Vakgroep Alfa-informatica & BCN
Rijksuniversiteit Groningen
**

Bernard Lang defines parsing as the calculation 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 concentrate 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 termination properties change drastically: we show that it is undecidable whether the intersection 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.

- Introduction
- The intersection of a CFG and a FSA
- The intersection of a DCG and a FSA
- Acknowledgments
- Bibliography
- About this document ...

1998-09-29