Head grammar

<h2 id="operations-on-headed-strings">Operations on headed strings</h2>
<h3>Wrapping</h3>
Wrapping is an operation on two headed strings defined as follows:
Let 
 
 
 
 α
 
 
 
 x
 ^
 
 
 
 β
 
 
 {\displaystyle \alpha {\widehat {x}}\beta }
 
 and 
 
 
 
 γ
 
 
 
 y
 ^
 
 
 
 δ
 
 
 {\displaystyle \gamma {\widehat {y}}\delta }
 
 be terminal strings headed by x and y, respectively.

 
 
 
 w
 (
 α
 
 
 
 x
 ^
 
 
 
 β
 ,
 γ
 
 
 
 y
 ^
 
 
 
 δ
 )
 =
 α
 x
 γ
 
 
 
 y
 ^
 
 
 
 δ
 β
 
 
 {\displaystyle w(\alpha {\widehat {x}}\beta ,\gamma {\widehat {y}}\delta )=\alpha x\gamma {\widehat {y}}\delta \beta }

<h3>Concatenation</h3>
Concatenation is a family of operations on n > 0 headed strings, defined for n = 1, 2, 3 as follows:
Let 
 
 
 
 α
 
 
 
 x
 ^
 
 
 
 β
 
 
 {\displaystyle \alpha {\widehat {x}}\beta }
 
, 
 
 
 
 γ
 
 
 
 y
 ^
 
 
 
 δ
 
 
 {\displaystyle \gamma {\widehat {y}}\delta }
 
, and 
 
 
 
 ζ
 
 
 
 z
 ^
 
 
 
 η
 
 
 {\displaystyle \zeta {\widehat {z}}\eta }
 
 be terminal strings headed by x, y, and z, respectively.

 
 
 
 
 c
 
 1
 ,
 0
 
 
 (
 α
 
 
 
 x
 ^
 
 
 
 β
 )
 =
 α
 
 
 
 x
 ^
 
 
 
 β
 
 
 {\displaystyle c_{1,0}(\alpha {\widehat {x}}\beta )=\alpha {\widehat {x}}\beta }

c
 
 2
 ,
 0
 
 
 (
 α
 
 
 
 x
 ^
 
 
 
 β
 ,
 γ
 
 
 
 y
 ^
 
 
 
 δ
 )
 =
 α
 
 
 
 x
 ^
 
 
 
 β
 γ
 y
 δ
 
 
 {\displaystyle c_{2,0}(\alpha {\widehat {x}}\beta ,\gamma {\widehat {y}}\delta )=\alpha {\widehat {x}}\beta \gamma y\delta }

c
 
 2
 ,
 1
 
 
 (
 α
 
 
 
 x
 ^
 
 
 
 β
 ,
 γ
 
 
 
 y
 ^
 
 
 
 δ
 )
 =
 α
 x
 β
 γ
 
 
 
 y
 ^
 
 
 
 δ
 
 
 {\displaystyle c_{2,1}(\alpha {\widehat {x}}\beta ,\gamma {\widehat {y}}\delta )=\alpha x\beta \gamma {\widehat {y}}\delta }

c
 
 3
 ,
 0
 
 
 (
 α
 
 
 
 x
 ^
 
 
 
 β
 ,
 γ
 
 
 
 y
 ^
 
 
 
 δ
 ,
 ζ
 
 
 
 z
 ^
 
 
 
 η
 )
 =
 α
 
 
 
 x
 ^
 
 
 
 β
 γ
 y
 δ
 ζ
 z
 η
 
 
 {\displaystyle 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
 
 
 (
 α
 
 
 
 x
 ^
 
 
 
 β
 ,
 γ
 
 
 
 y
 ^
 
 
 
 δ
 ,
 ζ
 
 
 
 z
 ^
 
 
 
 η
 )
 =
 α
 x
 β
 γ
 
 
 
 y
 ^
 
 
 
 δ
 ζ
 z
 η
 
 
 {\displaystyle 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
 
 
 (
 α
 
 
 
 x
 ^
 
 
 
 β
 ,
 γ
 
 
 
 y
 ^
 
 
 
 δ
 ,
 ζ
 
 
 
 z
 ^
 
 
 
 η
 )
 =
 α
 x
 β
 γ
 y
 δ
 ζ
 
 
 
 z
 ^
 
 
 
 η
 
 
 {\displaystyle 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
 ≤
 n
 <
 m
 
 
 {\displaystyle 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".

<h3>Form of rules</h3>
Head grammar rules are defined in terms of these two operations, with rules taking either of the forms

 
 
 
 X
 →
 w
 (
 α
 ,
 β
 )
 
 
 {\displaystyle X\to w(\alpha ,\beta )}

X
 →
 
 c
 
 m
 ,
 n
 
 
 (
 α
 ,
 β
 ,
 .
 .
 .
 )
 
 
 {\displaystyle X\to c_{m,n}(\alpha ,\beta ,...)}

where 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
, 
 
 
 
 β
 
 
 {\displaystyle \beta }
 
, ... are each either a terminal string or a non-terminal symbol.

<h2 id="example">Example</h2>
Head grammars are capable of generating the language 
 
 
 
 {
 
 a
 
 n
 
 
 
 b
 
 n
 
 
 
 c
 
 n
 
 
 
 d
 
 n
 
 
 :
 n
 ≥
 0
 }
 
 
 {\displaystyle \{a^{n}b^{n}c^{n}d^{n}:n\geq 0\}}
 
. We can define the grammar as follows:

 
 
 
 S
 →
 
 c
 
 1
 ,
 0
 
 
 (
 
 
 
 ϵ
 ^
 
 
 
 )
 
 
 {\displaystyle S\to c_{1,0}({\widehat {\epsilon }})}

S
 →
 
 c
 
 3
 ,
 1
 
 
 (
 
 
 
 a
 ^
 
 
 
 ,
 T
 ,
 
 
 
 d
 ^
 
 
 
 )
 
 
 {\displaystyle S\to c_{3,1}({\widehat {a}},T,{\widehat {d}})}

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

The derivation for "abcd" is thus:

 
 
 
 S
 
 
 {\displaystyle S}

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

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

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

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

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

a
 
 
 
 b
 ^
 
 
 
 c
 d
 
 
 {\displaystyle a{\widehat {b}}cd}

And for "aabbccdd":

 
 
 
 S
 
 
 {\displaystyle S}

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

c
 
 3
 ,
 1
 
 
 (
 
 
 
 a
 ^
 
 
 
 ,
 w
 (
 
 c
 
 3
 ,
 1
 
 
 (
 
 
 
 a
 ^
 
 
 
 ,
 w
 (
 S
 ,
 
 
 
 b
 ^
 
 
 
 c
 )
 ,
 
 
 
 d
 ^
 
 
 
 )
 ,
 
 
 
 b
 ^
 
 
 
 c
 )
 ,
 
 
 
 d
 ^
 
 
 
 )
 
 
 {\displaystyle 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
 
 
 (
 
 
 
 a
 ^
 
 
 
 ,
 w
 (
 
 c
 
 3
 ,
 1
 
 
 (
 
 
 
 a
 ^
 
 
 
 ,
 w
 (
 
 c
 
 1
 ,
 0
 
 
 (
 
 
 
 ϵ
 ^
 
 
 
 )
 ,
 
 
 
 b
 ^
 
 
 
 c
 )
 ,
 
 
 
 d
 ^
 
 
 
 )
 ,
 
 
 
 b
 ^
 
 
 
 c
 )
 ,
 
 
 
 d
 ^
 
 
 
 )
 
 
 {\displaystyle 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
 
 
 (
 
 
 
 a
 ^
 
 
 
 ,
 w
 (
 
 c
 
 3
 ,
 1
 
 
 (
 
 
 
 a
 ^
 
 
 
 ,
 w
 (
 
 
 
 ϵ
 ^
 
 
 
 ,
 
 
 
 b
 ^
 
 
 
 c
 )
 ,
 
 
 
 d
 ^
 
 
 
 )
 ,
 
 
 
 b
 ^
 
 
 
 c
 )
 ,
 
 
 
 d
 ^
 
 
 
 )
 
 
 {\displaystyle 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
 
 
 (
 
 
 
 a
 ^
 
 
 
 ,
 w
 (
 
 c
 
 3
 ,
 1
 
 
 (
 
 
 
 a
 ^
 
 
 
 ,
 
 
 
 b
 ^
 
 
 
 c
 ,
 
 
 
 d
 ^
 
 
 
 )
 ,
 
 
 
 b
 ^
 
 
 
 c
 )
 ,
 
 
 
 d
 ^
 
 
 
 )
 
 
 {\displaystyle c_{3,1}({\widehat {a}},w(c_{3,1}({\widehat {a}},{\widehat {b}}c,{\widehat {d}}),{\widehat {b}}c),{\widehat {d}})}

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

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

a
 a
 b
 
 
 
 b
 ^
 
 
 
 c
 c
 d
 d
 
 
 {\displaystyle aab{\widehat {b}}ccdd}

<h2 id="formal-properties">Formal properties</h2>
<h3>Equivalencies</h3>
Vijay-Shanker and Weir (1994)<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> demonstrate that <a href="/facts/Indexed_grammar/ckTIJC7D">linear indexed grammars</a>, <a href="/facts/Combinatory_categorial_grammar/UgtLoTG5">combinatory categorial grammar</a>, <a href="/facts/Tree-adjoining_grammar/gfr3weUw">tree-adjoining grammars</a>, and head grammars are <a href="/facts/Weak_equivalence_(formal_languages)/NVzANpS6">weakly equivalent</a> formalisms, in that they all define the same string languages.

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Pollard, C. 1984. Generalized Phrase Structure Grammars, Head Grammars, and Natural Language. Ph.D. thesis, Stanford University, CA. <a href="/wiki/Carl_Pollard" target="_blank">/wiki/Carl_Pollard</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Vijay-Shanker, K. and Weir, David J. 1994. The Equivalence of Four Extensions of Context-Free Grammars. Mathematical Systems Theory 27(6): 511-546. <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
</ol>

Head grammar open-in-new

Head grammar