Preset two-head automata and morphological analysis of natural language^∗

^∗This work was partially carried out under grants from the Social Sciences and Humanities Research Council of Canada, the Natural Sciences and Engineering Research Council of Canada, and the Information Technology Research Centre of Ontario.

Abstract

Modeling the morphological structure of natural languages in terms of a nondeterministic finite-state automaton is shown to be inadequate in its handling of some common natural language phenomena. We show that a two-tape nondeterministic automaton is capable of handling these phenomena. The modeling is improved by the specification of a new type of automaton, the preset two-head automaton, which we argue is equivalent in expressive power to a linear context-free grammar. We discuss the operation of a parser which implements the improved model.

Keywords:

• Morphology
• natural languages
• automata
• two-head automata
• preset two-head automata
• linear languages
• parsers

C.R.Categories:

• I.2.7
• F.1.1.
• F.4.2

^∗This work was partially carried out under grants from the Social Sciences and Humanities Research Council of Canada, the Natural Sciences and Engineering Research Council of Canada, and the Information Technology Research Centre of Ontario.

^∗This work was partially carried out under grants from the Social Sciences and Humanities Research Council of Canada, the Natural Sciences and Engineering Research Council of Canada, and the Information Technology Research Centre of Ontario.

Notes

^∗This work was partially carried out under grants from the Social Sciences and Humanities Research Council of Canada, the Natural Sciences and Engineering Research Council of Canada, and the Information Technology Research Centre of Ontario.