Head grammar (HG ) is a grammar formalism introduced in Carl Pollard (1984)[ 1] 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
→
a
b
c
{\displaystyle A\to abc}
A
→
(
a
b
c
,
0
)
{\displaystyle A\to (abc,0)}
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
→
a
^
b
c
{\displaystyle A\to {\widehat {a}}bc}
Two fundamental operations are then added to all rewrite rules: wrapping and concatenation.
Operations on headed strings
Wrapping
Wrapping is an operation on two headed strings defined as follows:
Let
α
x
^
β
{\displaystyle \alpha {\widehat {x}}\beta }
γ
y
^
δ
{\displaystyle \gamma {\widehat {y}}\delta }
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 }
Concatenation
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 }
ζ
z
^
η
{\displaystyle \zeta {\widehat {z}}\eta }
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}
m , with the head of string n designated as the head of the resulting string".
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 }
Example
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\}}
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
^
,
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
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}
Equivalencies
Vijay-Shanker and Weir (1994)[ 2] linear indexed grammars , combinatory categorial grammar , tree-adjoining grammars , and head grammars are weakly equivalent formalisms, in that they all define the same string languages.
References
^ Pollard, C. 1984. Generalized Phrase Structure Grammars, Head Grammars, and Natural Language . Ph.D. thesis, Stanford University, CA.^ Vijay-Shanker, K. and Weir, David J. 1994. The Equivalence of Four Extensions of Context-Free Grammars . Mathematical Systems Theory 27(6): 511-546.
Each category of languages, except those marked by a * , is a proper subset of the category directly above it. Any language in each category is generated by a grammar and by an automaton in the category in the same line.
