Head grammar (HG) is a grammar formalism introduced in Carl Pollard (1984) as an extension of the 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} might instead be A → ( a b c , 0 ) {\displaystyle A\to (abc,0)} , where the 0th terminal, the 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 } 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 }
… excerpt ends here. Continue reading the full article.
