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 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 }
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}
