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":