Compiling Regular Formalisms with Rule Features into Finite-State 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 gkiraz@research, bell-labs, tom 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 au- tomata. 1 Introduction The past few years have witnessed an increased in- terest in applying finite-state methods to language and speech problems. This in turn generated inter- est 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) accom- modate 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 morphol- ogy) would be difficult, if not impossible. Algo- rithms which compile regular grammars into au- tomata (Kaplan and Kay, 1994; Mohri and Sproat, 1996; Grimley-Evans, Kiraz, and Pulman, 1996) do not make use of this important mechanism. This pa- per 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 writ- ing'. The verbal pa"el measure 1, /katteb/~ 'wrote CAUSATIVE ACTIVE', is derived from the following 1Syriac verbs are classified under various measures (i.e., forms), the basic ones being p'al, pa "el and 'a/'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 voealism {ae} 'ACTIVE'. The morphemes produce the following un- derlying form: 3 a e [ [ */kateb/ J C V C V C I I k t b /katteb/is derived then by the gemination, implying CAUSATIVE, of the middle consonant, [t].4 The current work assumes knowledge of regular relations (Kaplan and Kay, 1994). The following convention has been adopted. Lexical forms (e.g., morphemes in morphology) appear in braces, { }, phonological segments in square brackets, [], and elements of tuples in angle brackets, (). Section 2 describes a regular formalism with rule features. Section 3 introduce a number of mathe- matical operators used in the compilation process. Sections 4 and 5 present our algorithm. Finally, sec- tion 6 provides an evaluation and some concluding remarks. 2 Regular Formalism with Rule Features This work adopts the following notation for regular formalisms, cf. (Kaplan and Kay, 1994): r ( =~, <=,<~ } A___p (1) where T, A and p are n-way regular expressions which describe same-length relations) (An n-way regu- lar expression is a regular expression whose terms 3This analysis is along the lines of (McCarthy, 1981) - based on autosegmental phonology (Goldsmith, 1976). 4This derivation is based on the linguistic model pro- posed by (Kiraz, 1996). ~More 'user-friendly' notations which allow mapping expressions of unequal length (e.g., (Grimley-Evans, Ki- raz, and …

Content truncated to 500 words