Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
A new class of formal languages will be defined the Distributed Index Languages (DI-languages). The grammar-formalism generating the new class - the DI-grammars - cover unbound dependencies in a rather natural way. The place of DI-languages in the Chomsky-hierarchy will be determined: Like Aho's indexed Languages, DI-languages represent a proper subclass of Type 1 (contextsensitive languages) and properly include Type 2 (context-free languages), but the DI-class is neither a subclass nor a superclass of Aho's indexed class. . | New Frontiers beyond Context-freeness DI-Grammars and DI-Automata. Peter Staudacher Institut fur Allgemeine und Indogermanische Sprachwissenschaft Universitat Regensburg Postfach 397 8400 Regensburg 1 Germany Abstract A new class of formal languages will be defined - the Distributed Index Languages DI-lan-guages . The grammar-formalism generating the new class - the Dl grammars - cover unbound dependencies in a rather natural way. The place of Dl-languages in the Chomsky-hierarchy will be determined Like Aho s indexed Languages Dl-languages represent a proper subclass of Type 1 contextsensitive languages and properly include Type 2 context-free languages but the DI-class is neither a subclass nor a superclass of Aho s indexed class. It will be shown that apart from DI-grammars Dl-languages can equivalently be characterized by a special type of automata - Dl-automata. Finally the time complexity of the recognition-problem for an interesting subclass of DI-Grammars will approximately be determined. 1 Introduction It is common practice to parse nested Wh-dependen-cies like the classical example of Rizzi 1982 in 1 1 Tuo fratello a cuijj mi domando che storie 2 abbiano raccontato t2 tp era molto preoccupato Your Brother to whom J I wonder which sto-ries 2 they told t2 t was very troubled using a stack mechanism. Under the binary branching hypothesis the relevant structure of 1 augmented by wh-stacks is as follows 2 a cui I mi domando Lpush - t J - Ị pus i t2 ti I che storie 2abbiano V2 t2 tj v1 PPỊtil I vjo NP t2 wp I I pop I raccontato t2 t Up to now it is unclear how far beyond context-freeness the generative power of a Type 2 grammar formalism is being extended if such a stack mechanism is grafted on it assuming of course that an upper bound for the size of the stack can not be motivated . Fernando Pereira s concept of Extraposition Grammar XG introduced in his influential paper Pereira 1981 1983 cf. Stabler 1987 in order to delimit the new territory can be shown to
