Context-free grammar

Although adequate models of human language for syntactic analysis and semantic interpretation are of at least contextfree complexity, for applications such as speech processing in which speed is important finite-state models are often preferred. These requirements may be reconciled by using the more complex grammar to automatically derive a finite-state approximation which can then be used as a filter to guide speech recognition or to reject many hypotheses at an early stage of processing.

8p bunthai_1 06-05-2013 47 4   Download

We prove in this paper that unordered, or I D / L P grammars, are e.xponentially more succinct than contextfree grammars, by exhibiting a sequence (L,~) of finite languages such that the size of any CFG for L,~ must grow exponentially in n, but which can be described by polynomial-size I D / L P grammars. The results have implications for the description of free word order languages.

5p bungio_1 03-05-2013 51 1   Download

This paper describes an algorithm for computing optimal structural descriptions for Optimality Theory grammars with context-free position structures. This algorithm extends Tesar's dynamic programming approach (Tesar, 1994) (Tesar, 1995@ to computing optimal structural descriptions from regular to context-free structures. The generalization to contextfree structures creates several complications, all of which are overcome without compromising the core dynamic programming approach.

7p bunmoc_1 20-04-2013 46 1   Download

We show that the class of string languages generated by linear context-free rewriting systems is equal to the class of output languages of deterministic treewalking transducers. From equivalences that have previously been established we know that this class of languages is also equal to the string languages generated by context-free hypergraph grammars, multicomponent tree-adjoining grammars, and multiple contextfree grammars and to the class of yields of images of the regular tree languages under finite-copying topdown tree transducers. ...

8p bunmoc_1 20-04-2013 40 1   Download

Phrase-structure grammars are an effective representation for important syntactic and semantic aspects of natural languages, but are computationally too demanding for use as language models in real-time speech recognition. An algorithm is described that computes finite-state approximations for context-free grammars and equivalent augmented phrase-structure grammar formalisms. The approximation is exact for certain contextfree grammars generating regular languages, including all left-linear and right-linear context-free grammars. ...

10p bunmoc_1 20-04-2013 32 1   Download

The paper presents a tabular interpretation for a kind of 2-Stack Automata. These automata may be used to describe various parsing strategies, ranging from purely top-down to purely bottom-up, for LIGs and TAGs. The tabular interpretation ensures, for all strategies, a time complexity in O(n 6) and space complexity in O(n 5) where n is the length of the input string.

7p bunrieu_1 18-04-2013 36 2   Download

Unification grammars are widely accepted as an expressive means for describing the structure of natural languages. In general, the recognition problem is undecidable for unification grammars. Even with restricted variants of the formalism, offline parsable grammars, the problem is computationally hard. We present two natural constraints on unification grammars which limit their expressivity. We first show that non-reentrant unification grammars generate exactly the class of contextfree languages.

8p hongvang_1 16-04-2013 40 1   Download

We present a method for the computation of prefix probabilities for synchronous contextfree grammars. Our framework is fairly general and relies on the combination of a simple, novel grammar transformation and standard techniques to bring grammars into normal forms.

10p hongdo_1 12-04-2013 39 1   Download

This tutorial overviews basic ideas of TAG/ CCG/LFG/HPSG, and provides attendees with a comparison of these formalisms from a linguistic and computational point of view. We start from stating the motivation behind using these expressive grammar formalisms for NLP, contrasting them with shallow formalisms like contextfree grammars.

1p hongdo_1 12-04-2013 62 5   Download

We propose a corpus-based probabilistic framework to extract hidden common syntax across languages from non-parallel multilingual corpora in an unsupervised fashion. For this purpose, we assume a generative model for multilingual corpora, where each sentence is generated from a language dependent probabilistic contextfree grammar (PCFG), and these PCFGs are generated from a prior grammar that is common across languages.

5p hongdo_1 12-04-2013 32 2   Download

This paper describes a model of syntactical analysis. It shows first how a context-free grammar formalism can be modified in order to reduce the number of rules required by a natural language, and second, how this formalism can be extended to the handling of some non-contextfree phenomena. The description of the algorithm is also given.

11p nghetay_1 06-04-2013 36 1   Download