Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
The problem of transforming a lattice into a non-deterministic finite state automaton is non-trivial. We present a transformation algorithm which tracks, for each node of an automaton under construction, the larcs which it reflects and the lattice nodes at their origins and extremities. An extension of the algorithm permits the inclusion of null, or epsilon, arcs in the output automaton. The algorithm has been successfully applied to lattices derived from dictionaries, i.e. very large corpora of strings. . | Transforming Lattices into Non-deterministic Automata with Optional Null Arcs Mark Seligman Christian Boitet Boubaker Meddeb-Hamrouni Université Joseph Fourier GETA CLIPS IMAG-campus BP 53 150 rue de la Chimie 38041 Grenoble Cedex 9 France seligman@cerf.net Christian.Boitet Boubaker.Meddeb-Hamrouni @imag. fr Abstract The problem of transforming a lattice into a non-deterministic finite state automaton is non-trivial. We present a transformation algorithm which tracks for each node of an automaton under construction the lares which it reflects and the lattice nodes at their origins and extremities. An extension of the algorithm permits the inclusion of null or epsilon arcs in the output automaton. The algorithm has been successfully applied to lattices derived from dictionaries i.e. very large corpora of strings. Introduction Linguistic data grammars speech recognition results etc. are sometimes represented as lattices and sometimes as equivalent finite state automata. While the transformation of automata into lattices is straightforward we know of no algorithm in the current literature for transforming a lattice into a non-deterministic finite state automaton. See e.g. Hopcroft et al 1979 Aho et al 1982 . We describe such an algorithm here. Its main feature is the maintenance of complete records of the relationships between objects in the input lattice and their images on an automaton as these are added during transformation. An extension of the algorithm permits the inclusion of null or epsilon arcs in the output automaton. The method we present is somewhat complex but we have thus far been unable to discover a simpler one. One suggestion illustrates the difficulties this proposal was simply to slide lattice node labels leftward onto their incoming arcs and then starting with the final lattice node to merge nodes with identical outgoing arc sets. This strategy does successfully transform many lattices but fails on lattices like this one For this lattice the .
