シリアル間の依存関係

言語学では、 2つの単語の系列間の依存関係を表す線が互いに交差するときに、交差系列依存関係（一部の著者は交差依存関係とも呼ぶ^{[1] ）が発生します。 [2]}これらは、自然言語の統語構造を決定したい言語学者にとって特に興味深いものです。任意の数の交差系列依存関係を含む言語は非文脈自由です。この事実により、オランダ語^[3]とスイスドイツ語^[4]は非文脈自由であることが証明されています。

スイスドイツ語では動詞とその項を連続的に並べることができるので、シーバーの例を次に示します。^[4]

つまり、「私たちはハンスが家を塗装するのを手伝います。」

連続する名詞句em Hans (ハンス) とes huus (家)、および連続する動詞hälfed ( help ) とaastriiche ( paint ) は両方とも 2 つの別個の一連の構成要素を形成していることに注意してください。与格動詞 hälfedと対格動詞 aastriiche は、それぞれ与格em Hansと対格es huus を引数として 取ることにも注意してください。

をすべてのスイスドイツ語の文の集合とします。 が文脈自由ではないことを数学的に証明します。 ${\displaystyle L_{SG}}$${\displaystyle L_{SG}}$

スイスドイツ語の文では、文法的な格（与格または目的格）の動詞の数は、その格の目的語の数と一致しなければなりません。さらに、任意の数のそのような目的語を含む文は（原則として）許容されます。したがって、のサブセットである次の形式言語を定義できます。したがって、 が得られます。ここで、はによって定義される正規言語です。ここで、上付きのプラス記号は「1つ以上のコピー」を意味します。文脈自由言語の集合は正規言語との交差に関して閉じているため、 が文脈自由でないことを証明するだけで済みます（、^[5] pp 130–135）。 ${\displaystyle L_{SG}}$$${\displaystyle L={\text{De Jan}}{\text{ s}}{\ddot {\mathrm {a} }}{\text{it}}{\text{ das}}{\text{ mer }}{\text{ (d'chind)}}{}^{m}{\text{ (em}}{\text{ ハンス)}}{}^{n}{\text{ s}}{\ text{ huus}}{\text{ h}}{\ddot {\mathrm {a} }}{\text{nd}}{\text{ wele}}{\text{ (laa)}}{}^{m}{\text{ (h}}{\ddot {\ mathrm {a} }}{\text{lfe)}}{}^{n}{\text{ aastriiche.}}}$$${\displaystyle L=L_{SG}\cap L_{r}}$${\displaystyle L_{r}}$$${\displaystyle L={\text{De Jan}}{\text{ s}}{\ddot {\mathrm {a} }}{\text{it}}{\text{ das}}{\text{ mer }}{\text{ (d'chind)}}{}^{+}{\text{ (em}}{\text{ ハンス)}}{}^{+}{\text{ s}}{\ text{ huus}}{\text{ h}}{\ddot {\mathrm {a} }}{\text{nd}}{\text{ wele}}{\text{ (laa)}}{}^{+}{\text{ (h}}{\ddot {\ mathrm {a} }}{\text{lfe)}}{}^{+}{\text{ aastriiche.}}}$$${\displaystyle L}$

単語の置換後、は の形になります。 は に次の写像で写像できるので、であり、文脈自由言語は終端記号から終端文字列への写像（つまり、準同型）に関して閉じているため（、^[5] pp 130–135）、 が文脈自由でないことを証明するだけで済みます。 ${\displaystyle L}$${\displaystyle \{xa^{m}b^{n}yc^{m}d^{n}z|m,n\geq 1\}}$${\displaystyle L}$${\displaystyle L'}$${\displaystyle x,y,z\mapsto \epsilon ;a\mapsto a;b\mapsto b;c\mapsto c}$${\displaystyle L'}$

${\displaystyle L'=\{a^{m}b^{n}c^{m}d^{n}|m,n\geq 1\}}$は非文脈自由言語の標準的な例である（, ^{[5] p. 128）。これは}オグデンの補題によって示され得る。

言語が文脈自由文法によって生成されると仮定し、 をオグデンの補題で要求される長さとし、言語内の単語を考え、文字 にマークを付けます。すると、オグデンの補題によって暗示される 3 つの条件をすべて満たすことはできません。${\displaystyle p}$${\displaystyle a^{p}b^{p}c^{p}d^{p}}$${\displaystyle b^{p}c^{p}}$

クロスシリアル依存性を含む既知の音声言語はすべて、同様に文脈自由ではないことが証明されています。^{[2]これにより、1980年代に自然言語でクロスシリアル依存性が特定されると、}一般化句構造文法は放棄されました。^[6]

軽度文脈依存言語の研究では、自然言語に見られるような文脈依存を再現できる、より狭く計算的に扱いやすい文脈依存言語のサブクラスを特定しようと試みられてきた。例えば、クロスシリアル依存性は線形文脈自由書き換えシステム（LCFRS）で表現でき、例えば{ a ⁿ b ⁿ c ⁿ d ⁿ | n ≥ 1}のLCFRS文法を書くことができる。^{[7] [8] [9]}