• Images
• Videos
• Documents
• Books
• Articles

Operations on headed strings

Wrapping

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 }

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 } , 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".

Form of rules

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.

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\}} . 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 ^ , 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}

Formal properties

Equivalencies

Vijay-Shanker and Weir (1994)² demonstrate that 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

1. Pollard, C. 1984. Generalized Phrase Structure Grammars, Head Grammars, and Natural Language. Ph.D. thesis, Stanford University, CA. /wiki/Carl_Pollard ↩

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. ↩