Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo khoa học: "Compiling Regular Formalisms with Rule Features into Finite-State Automata"
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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 gkirazOresearch.bell-labs.com 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 e.g. 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 i.e. 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 .