tailieunhanh - Báo cáo khoa học: "Compiling Regular Formalisms with Rule Features into Finite-State Automata"

This paper presents an algorithm for the compilation of regular formalisms with rule features into finite-state automata. Rule features are incorporated into the right context of rules. This general notion can also be applied to other algorithms which compile regular rewrite rules into automata. | Compiling Regular Formalisms with Rule Features into Finite-State Automata George Anton Kiraz Bell Laboratories Lucent Technologies 700 Mountain Ave. Murray Hill NJ 07974 USA Abstract This paper presents an algorithm for the compilation of regular formalisms with rule features into finite-state automata. Rule features are incorporated into the right context of rules. This general notion can also be applied to other algorithms which compile regular rewrite rules into automata. 1 Introduction The past few years have witnessed an increased interest in applying finite-state methods to language and speech problems. This in turn generated interest in devising algorithms for compiling rules which describe regular languages relations into finite-state automata. It has long been proposed that regular formalisms . rewrite rules two-level formalisms accommodate rule features which provide for finer and more elegant descriptions Bear 1988 . Without such a mechanism writing complex grammars say two-level grammars for Syriac or Arabic morphology would be difficult if not impossible. Algorithms which compile regular grammars into automata Kaplan and Kay 1994 Mohri and Sproat 1996 Grimley-Evans Kiraz and Pulman 1996 do not make use of this important mechanism. This paper presents a method for incorporating rule features in the resulting automata. The following Syriac example is used here with the infamous Semitic root ktb notion of writing . The verbal pa el measure1 katteb 2 wrote CAUSATIVE active is derived from the following Syriac verbs are classified under various measures . forms the basic ones being p al pa el and af el. 2Spirantization is ignored here for a discussion on Syriac spirantization see Kiraz 1995 . morphemes the pattern cvcvc verbal pattern the above mentioned root and the vocalism ae active . The morphemes produce the following underlying form 3 a e c V c V c kateb k t b katteb is derived then by the gemination implying .