Operations on headed strings
Wrapping
Wrapping is an operation on two headed strings defined as follows:
Let
and
be terminal strings headed by x and y, respectively.
Concatenation
Concatenation is a family of operations on n > 0 headed strings, defined for n = 1, 2, 3 as follows:
Let
,
, and
be terminal strings headed by x, y, and z, respectively.
And so on for
. 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
where
,
, ... are each either a terminal string or a non-terminal symbol.
Example
Head grammars are capable of generating the language
. We can define the grammar as follows:
The derivation for "abcd" is thus:
And for "aabbccdd":