Head_grammar
ヘッド文法（HG ）は、文脈自由文法クラスの文法の拡張として、Carl Pollard（1984）で導入された文法形式です。したがって、ヘッド文法は、依存文法とは対照的に、句構造文法の一種です。ヘッド文法のクラスは、線形文脈自由書き換えシステムのサブセットです。
ヘッド文法を定義する一般的な方法の1つは、CFGの終端文字列をインデックス付きの終端文字列に置き換えることです。ここで、インデックスは文字列の「ヘッド」ワードを示します。したがって、たとえば、次のようなCFルールA a b c
{ A to abc}
代わりに A （（ ab c 0 ）。 { A to（abc、0）}
、ここで、0番目の端末aは、結果の端末文字列の先頭です。表記の便宜上、このようなルールは、次のように、ヘッド端子が何らかのマークで示されている、単なる端子文字列として記述できます。A a ^ b c
{ A to { widehat {a}} bc} 次に、ラッピングと連結という2つの基本的な操作がすべての書き換えルールに追加されます。
コンテンツ
1 頭付き文字列の操作
1.1 ラッピング 1.2 連結 1.3 ルールの形式
2 例
3 正式なプロパティ
3.1 同等性
4 参考文献
頭付き文字列の操作編集
ラッピング
ラッピングは、次のように定義された2つの頭の文字列に対する操作です。
させてαX ^ β
{ alpha { widehat {x}} beta}
とγ y ^ δ
{ gamma { widehat {y}} delta}
それぞれxとyで始まる終端文字列である。 w （（ αX ^ β γy ^ δ
）。= αX γ y ^ δ β
{ w（ alpha { widehat {x}} beta、 gamma { widehat {y}} delta）= alpha x gamma { widehat {y}} delta beta}
連結
連結は、n> 0の見出し付き文字列に対する一連の操作であり、n = 1、2、3に対して次のように定義されます。
させてαX ^ β
{ alpha { widehat {x}} beta}
、γ y ^ δ
{ gamma { widehat {y}} delta}
、 とζ z ^ η
{ zeta { widehat {z}} eta}
それぞれx、y、zで始まる終端文字列である。c 1 0（（ αX^ β
）。= αX ^ β
{ c_ {1，0}（ alpha { widehat {x}} beta）= alpha { widehat {x}} beta}
c 2 0 （（ αX ^ β γy ^ δ
）。= αX ^ β γ y δ
{ c_ {2，0}（ alpha { widehat {x}} beta、 gamma { widehat {y}} delta）= alpha { widehat {x}} beta gamma y デルタ }
c 2 1 （（ αX ^ β γy ^ δ
）。= αX β γ y ^ δ
{ c_ {2，1}（ alpha { widehat {x}} beta、 gamma { widehat {y}} delta）= alpha x beta gamma { widehat {y}} デルタ }
c 3 0 （（ αX ^ β γy ^
δ ζz ^ η
）。= αX ^ β γ y δ ζ z =0
{ 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 =0
{ 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 ^ =0
{ 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}
など c m n 0≤ n { c_ {m、n}：0 leq n
。ここでパターンを簡単にまとめると、「いくつかの終端文字列mを連結し、文字列nの頭を結果の文字列の頭として指定します」。
ルールの形式
ヘッド文法ルールは、これら2つの操作の観点から定義され、ルールはいずれかの形式を取ります。X w （（ α β ）。 { X to w（ alpha、 beta）}
Xc m n（（ α β
、 。 ）。
{ X to c_ {m、n}（ alpha、 beta、…）}
どこ α { alpha}
、 β { beta}
、…は、それぞれ終端記号または非終端記号のいずれかです。
例
ヘッド文法は言語を生成することができます
{{a n b n c n d n
：n ≥ 0 }
{ {a ^ {n} b ^ {n} c ^ {n} d ^ {n}：n geq 0 }}
。文法は次のように定義できます。S c 1 0（（ ϵ ^ ）。
{ S to c_ {1，0}（{ widehat { epsilon}}）}
S c 3 1 （ a ^ T d ^ ）。
{ S to c_ {3，1}（{ widehat {a}}、T、{ widehat {d}}）}
T w（（ S b^ c ）。 { T to w（S、{ widehat {b}} c）}
したがって、「abcd」の派生は次のとおりです。 S { S}
c 3 1 （（ a
^ T d ^ ）。
{ c_ {3，1}（{ widehat {a}}、T、{ widehat {d}}）}
c 3 1 （（ a ^ w （（ S b^ c
）。 d ^ ）。
{ c_ {3，1}（{ widehat {a}}、w（S、{ widehat {b}} c）、{ widehat {d}}）}
c 3 1 （（ a ^ w （（ c 1 0 （（ ϵ ^ ）。 b^ c
）。 d ^ ）。
{ c_ {3，1}（{ widehat {a}}、w（c_ {1，0}（{ widehat { epsilon}}）、{ widehat {b}} c）、{ widehat {d}}）}
c 3 1 （（ a ^ w （（ ϵ
^ b^ c
）。 d ^ ）。
{ c_ {3，1}（{ widehat {a}}、w（{ widehat { epsilon}}、{ widehat {b}} c）、{ widehat {d}}）}
c 3 1 （（ a
^ b^ c d ^ ）。 { c_ {3，1}（{ widehat {a}}、{ widehat {b}} c、{ widehat {d}}）}
a b ^ c d
{ a { widehat {b}} cd}
そして「aabbccdd」の場合： S { S}
c 3 1 （（ a
^ T d ^ ）。
{ c_ {3，1}（{ widehat {a}}、T、{ widehat {d}}）}
c 3 1 （（ a ^ w （（ S b^ c
）。 d ^ ）。
{ 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 ^ ）。
{ 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 ^ ）。
{ 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 ^ ）。
{ 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 ^ ）。
{ 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 ^ ）。
{ 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 （（ ab ^ c d b ^ c
）。 d ^ ）。
{ c_ {3，1}（{ widehat {a}}、w（a { widehat {b}} cd、{ widehat {b}} c）、{ widehat {d}}）}
c 3 1 （（ a
^ ab b ^ c c d d ^ ）。 { c_ {3，1}（{ widehat {a}}、ab { widehat {b}} ccd、{ widehat {d}}）}
a a b b ^ c c d d
{ aab { widehat {b}} ccdd}
正式なプロパティ編集
同等性
Vijay-Shanker and Weir（1994）は、線形索引文法、組み合わせ範疇文法、木接合文法、および頭文法は、すべて同じ文字列言語を定義するという点で、弱く同等の形式であることを示しています。
参考文献
^ Pollard、C. 1984.一般化句構造文法、頭の文法、および自然言語。博士号 論文、スタンフォード大学、カリフォルニア州。
^ Vijay-Shanker、K. and Weir、 DavidJ.1994.文脈自由文法の4つの拡張の同等性。数学システム理論27（6）：511-546。”