Kalpana Kalpana (Editor)

Generalized context free grammar

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

Generalized Context-free Grammar (GCFG) is a grammar formalism that expands on context-free grammars by adding potentially non-context free composition functions to rewrite rules. Head grammar (and its weak equivalents) is an instance of such a GCFG which is known to be especially adept at handling a wide variety of non-CF properties of natural language.

Contents

Description

A GCFG consists of two components: a set of composition functions that combine string tuples, and a set of rewrite rules. The composition functions all have the form f ( ⟨ x 1 , . . . , x m ⟩ , ⟨ y 1 , . . . , y n ⟩ , . . . ) = γ , where γ is either a single string tuple, or some use of a (potentially different) composition function which reduces to a string tuple. Rewrite rules look like X → f ( Y , Z , . . . ) , where Y , Z , ... are string tuples or non-terminal symbols.

The rewrite semantics of GCFGs is fairly straightforward. An occurrence of a non-terminal symbol is rewritten using rewrite rules as in a context-free grammar, eventually yielding just compositions (composition functions applied to string tuples or other compositions). The composition functions are then applied, successively reducing the tuples to a single tuple.

Example

A simple translation of a context-free grammar into a GCFG can be performed in the following fashion. Given the grammar in (1), which generates the palindrome language { w w R : w ∈ { a , b } ∗ } , where w R is the string reverse of w , we can define the composition function conc as in (2a) and the rewrite rules as in (2b).

The CF production of abbbba is

S aSa abSba abbSbba abbbba

and the corresponding GCFG production is

S → c o n c ( ⟨ a ⟩ , S , ⟨ a ⟩ ) c o n c ( ⟨ a ⟩ , c o n c ( ⟨ b ⟩ , S , ⟨ b ⟩ ) , ⟨ a ⟩ ) c o n c ( ⟨ a ⟩ , c o n c ( ⟨ b ⟩ , c o n c ( ⟨ b ⟩ , S , ⟨ b ⟩ ) , ⟨ b ⟩ ) , ⟨ a ⟩ ) c o n c ( ⟨ a ⟩ , c o n c ( ⟨ b ⟩ , c o n c ( ⟨ b ⟩ , c o n c ( ⟨ ϵ ⟩ , ⟨ ϵ ⟩ , ⟨ ϵ ⟩ ) , ⟨ b ⟩ ) , ⟨ b ⟩ ) , ⟨ a ⟩ ) c o n c ( ⟨ a ⟩ , c o n c ( ⟨ b ⟩ , c o n c ( ⟨ b ⟩ , ⟨ ϵ ⟩ , ⟨ b ⟩ ) , ⟨ b ⟩ ) , ⟨ a ⟩ ) c o n c ( ⟨ a ⟩ , c o n c ( ⟨ b ⟩ , ⟨ b b ⟩ , ⟨ b ⟩ ) , ⟨ a ⟩ ) c o n c ( ⟨ a ⟩ , ⟨ b b b b ⟩ , ⟨ a ⟩ ) ⟨ a b b b b a ⟩

Linear Context-free Rewriting Systems (LCFRSs)

Weir (1988) describes two properties of composition functions, linearity and regularity. A function defined as f ( x 1 , . . . , x n ) = . . . is linear if and only if each variable appears at most once on either side of the =, making f ( x ) = g ( x , y ) linear but not f ( x ) = g ( x , x ) . A function defined as f ( x 1 , . . . , x n ) = . . . is regular if the left hand side and right hand side have exactly the same variables, making f ( x , y ) = g ( y , x ) regular but not f ( x ) = g ( x , y ) or f ( x , y ) = g ( x ) .

A grammar in which all composition functions are both linear and regular is called a Linear Context-free Rewriting System (LCFRS). LCFRS is a proper subclass of the GCFGs, i.e. it has strictly less computational power than the GCFGs as a whole.

On the other hand, LCFRSs are strictly more expressive than linear-indexed grammars and their weakly equivalent variant tree adjoining grammars (TAGs). Head grammar is another example of an LCFRS that is strictly less powerful than the class of LCFRSs as a whole.

LCFRS are weakly equivalent to (set-local) multicomponent TAGs (MCTAGs) and also with multiple context-free grammar (MCFGs [1]). and minimalist grammars (MGs). The languages generated by LCFRS (and their weakly equivalents) can be parsed in polynomial time.

References

Generalized context-free grammar Wikipedia
(Text) CC BY-SA


Similar Topics