Capturing CFLs with Tree Adjoining Grammars

Capturing CFLs with Tree Adjoining James Rogers* Dept. of Computer and Information Sciences University of Delaware Newark, DE 19716, USA j rogers©cis, udel. edu Grammars Abstract We define a decidable class of TAGs that is strongly equivalent to CFGs and is cubic-time parsable. This class serves to lexicalize CFGs in the same manner as the LC, FGs of Schabes and Waters but with consider- ably less restriction on the form of the grammars. The class provides a nornlal form for TAGs that generate local sets m rnuch the same way that regular grammars provide a normal form for CFGs that generate regular sets. Introduction We introduce the notion of Regular Form for Tree Ad- joining (;rammars (TA(;s). The class of TAGs that are in regular from is equivalent in strong generative capacity 1 to the Context-Free Grammars, that is, the sets of trees generated by TAGs in this class are the local sets--the sets of derivation trees generated by CFGs. 2 Our investigations were initially motivated by the work of Schabes, Joshi, and Waters in lexicalization of CFGs via TAGs (Schabes and Joshi, 1991; Joshi and Schabes, 1992; Schabes and Waters, 1993a; Schabes and Waters, 1993b; Schabes, 1990). The class we describe not only serves to lexicalize CFGs in a way that is more faith- tiff and more flexible in its encoding than earlier work, but provides a basis for using the more expressive TAG formalism to define Context-Free Languages (CFLs.) In Schabes et al. (1988) and Schabes (1990) a gen- eral notion of lexicalized grammars is introduced. A grammar is lexicalized in this sense if each of the ba- sic structures it manipulates is associated with a lexical item, its anchor. The set of structures relevant to a particular input string, then, is selected by the lexical *The work reported here owes a great deal to extensive discussions with K. Vijay-Shanker. 1 We will refer to equivalence of the sets of trees generated by two grammars or classes of grammars as strong equiva- lence. Equivalence of their string languages will be referred to as weak equivalence. 2Technically, the sets of trees generated by TAGs in the class are recognizable sets. The local and recognizable sets are equivalent modulo projection. We discuss the distinction in the next section. items that occur in that string. There are a number of reasons for exploring lexicalized grammars. Chief among these are linguistic considerations--lexicalized grammars reflect the tendency in many current syntac- tic theories to have the details of the syntactic structure be projected from the lexicon. There are also practical advantages. All lexicalized grammars are finitely am- biguous and, consequently, recognition for them is de- cidable. Further, lexicalization supports strategies that can, in practice, improve the speed of recognition algo- rithms (Schabes et M., 1988). One grammar formalism is said to lezicalize an- other (Joshi and Schabes, 1992) if for every grammar in the second formalism there is a lexicalized grammar in the first that generates exactly the same set of struc- tures. …

Content truncated to 500 words