World Library  
Flag as Inappropriate
Email this Article

Head grammar

Article Id: WHEBN0026102914
Reproduction Date:

Title: Head grammar  
Author: World Heritage Encyclopedia
Language: English
Subject: Tree-adjoining grammar, Carl Pollard
Publisher: World Heritage Encyclopedia

Head grammar

Head Grammar (HG) is a grammar formalism introduced in Carl Pollard (1984)[1] as an extension of the Context-free grammar class of grammars. Head Grammar is therefore a type of phrase structure grammar, as opposed to a dependency grammar. The class of head grammars is a subset of the linear context-free rewriting systems.

One typical way of defining head grammars is to replace the terminal strings of CFGs with indexed terminal strings, where the index denotes the "head" word of the string. Thus, for example, a CF rule such as A \to abc might instead be A \to (abc, 0), where the 0th terminal, the a, is the head of the resulting terminal string. For convenience of notation, such a rule could be written as just the terminal string, with the head terminal denoted by some sort of mark, as in A \to \widehat{a}bc.

Two fundamental operations are then added to all rewrite rules: wrapping and concatenation.

Operations on Headed Strings


Wrapping is an operation on two headed strings defined as follows:

Let \alpha \widehat{x} \beta and \gamma \widehat{y} \delta be terminal strings headed by x and y, respectively.

w(\alpha \widehat{x} \beta, \gamma \widehat{y} \delta) = \alpha x \gamma \widehat{y} \delta \beta


Concatenation is a family of operations on n > 0 headed strings, defined for n = 1, 2, 3 as follows:

Let \alpha \widehat{x} \beta, \gamma \widehat{y} \delta, and \zeta \widehat{z} \eta be terminal strings headed by x, y, and z, respectively.

c_{1,0}(\alpha \widehat{x} \beta) = \alpha \widehat{x} \beta

c_{2,0}(\alpha \widehat{x} \beta, \gamma \widehat{y} \delta) = \alpha \widehat{x} \beta \gamma y \delta

c_{2,1}(\alpha \widehat{x} \beta, \gamma \widehat{y} \delta) = \alpha x \beta \gamma \widehat{y} \delta

c_{3,0}(\alpha \widehat{x} \beta, \gamma \widehat{y} \delta, \zeta \widehat{z} \eta) = \alpha \widehat{x} \beta \gamma y \delta \zeta z \eta

c_{3,1}(\alpha \widehat{x} \beta, \gamma \widehat{y} \delta, \zeta \widehat{z} \eta) = \alpha x \beta \gamma \widehat{y} \delta \zeta z \eta

c_{3,2}(\alpha \widehat{x} \beta, \gamma \widehat{y} \delta, \zeta \widehat{z} \eta) = \alpha x \beta \gamma y \delta \zeta \widehat{z} \eta

And so on for c_{m,n} : 0 \leq n < m. One can sum up the pattern here simply as "concatenate some number of terminal strings m, with the head of string n designated as the head of the resulting string".

Form of Rules

Head Grammar rules are defined in terms of these two operations, with rules taking either of the forms

X \to w(\alpha, \beta)

X \to c_{m,n}(\alpha, \beta, ...)

where \alpha, \beta, ... are each either a terminal string or a non-terminal symbol.


Head Grammars are capable of generating the language \{ a^n b^n c^n d^n : n \geq 0 \}. We can define the grammar as follows:

S \to c_{1,0}(\widehat{\epsilon})

S \to c_{3,1}(\widehat{a}, T, \widehat{d})

T \to w(S, \widehat{b}c)

The derivation for "abcd" is thus:


c_{3,1}(\widehat{a}, T, \widehat{d})

c_{3,1}(\widehat{a}, w(S, \widehat{b}c), \widehat{d})

c_{3,1}(\widehat{a}, w(c_{1,0}(\widehat{\epsilon}), \widehat{b}c), \widehat{d})

c_{3,1}(\widehat{a}, w(\widehat{\epsilon}, \widehat{b}c), \widehat{d})

c_{3,1}(\widehat{a}, \widehat{b}c, \widehat{d})


And for "aabbccdd":


c_{3,1}(\widehat{a}, T, \widehat{d})

c_{3,1}(\widehat{a}, w(S, \widehat{b}c), \widehat{d})

c_{3,1}(\widehat{a}, w(c_{3,1}(\widehat{a}, T, \widehat{d}), \widehat{b}c), \widehat{d})

c_{3,1}(\widehat{a}, w(c_{3,1}(\widehat{a}, w(S, \widehat{b}c), \widehat{d}), \widehat{b}c), \widehat{d})

c_{3,1}(\widehat{a}, w(c_{3,1}(\widehat{a}, w(c_{1,0}(\widehat{\epsilon}), \widehat{b}c), \widehat{d}), \widehat{b}c), \widehat{d})

c_{3,1}(\widehat{a}, w(c_{3,1}(\widehat{a}, w(\widehat{\epsilon}, \widehat{b}c), \widehat{d}), \widehat{b}c), \widehat{d})

c_{3,1}(\widehat{a}, w(c_{3,1}(\widehat{a}, \widehat{b}c, \widehat{d}), \widehat{b}c), \widehat{d})

c_{3,1}(\widehat{a}, w(a\widehat{b}cd, \widehat{b}c), \widehat{d})

c_{3,1}(\widehat{a}, ab\widehat{b}ccd, \widehat{d})


Formal Properties


Vijay-Shanker and Weir (1994)[2] demonstrates that Linear Indexed Grammars, Combinatory Categorial Grammars, Tree-adjoining Grammars, and Head Grammars are weakly equivalent formalisms, in that they all define the same string languages.


This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.