ダイク言語

Language consisting of balanced strings of brackets

計算機科学、数学、言語学における形式言語理論において、ダイク語とは括弧のつり合いのとれた列である。ダイク語の集合はダイク言語を構成する。最も単純なダイク1は、対応する括弧を2つだけ用いる（例えば ( と )）。

ダイク語とダイク言語は、数学者ヴァルター・フォン・ダイクにちなんで名付けられました。これらは、算術式や代数式など、括弧の連続が正しく入れ子になっている必要がある式の解析に応用されます。

正式な定義

記号[と]からなるアルファベットをとします。そのクリーネ閉包を とします。ダイク言語は次のように定義されます。 ${\displaystyle \Sigma =\{[,]\}}$ ${\displaystyle \Sigma ^{*}}$

${\displaystyle \{u\in \Sigma ^{*}\vert {\text{ all prefixes of }}u{\text{ contain no more ]'s than ['s}}{\text{ and the number of ['s in }}u{\text{ equals the number of ]'s}}\}.}$

文脈自由文法

状況によっては、文脈自由文法を用いてDyck言語を定義すると役立つ場合があります。Dyck言語は、単一の非終端記号Sと以下の生成規則を持つ文脈自由文法によって生成されます。

S → ε | "[" S "]" S

つまり、Sは空の文字列( ε )であるか、または "[" (Dyck 言語の要素)、対応する "]"、および Dyck 言語の要素のいずれかです。

Dyck言語の代替文脈自由文法は、次の生成規則で与えられます。

S → （[" S "]"）^*

つまり、Sは、Dyck 言語の要素である "[ と対応する "] " の組み合わせの0 回以上の出現であり、生成規則の右側にある Dyck 言語の複数の要素は、互いに異なっていても構いません。

代替定義

さらに別の文脈では、次のように同値類に分割してDyck言語を定義する方が役に立つかもしれない。長さ の任意の元に対して、部分関数とを次のように定義する。 ${\displaystyle \Sigma ^{*}}$ ${\displaystyle u\in \Sigma ^{*}}$ ${\displaystyle |u|}$ ${\displaystyle \operatorname {insert} :\Sigma ^{*}\times \mathbb {N} \rightarrow \Sigma ^{*}}$ ${\displaystyle \operatorname {delete} :\Sigma ^{*}\times \mathbb {N} \rightarrow \Sigma ^{*}}$

${\displaystyle \operatorname {insert} (u,j)}$の位置に「 」が挿入されている ${\displaystyle u}$ ${\displaystyle []}$ ${\displaystyle j}$

${\displaystyle \operatorname {delete} (u,j)}$番目の位置から「 」が削除されています ${\displaystyle u}$ ${\displaystyle []}$ ${\displaystyle j}$

ただし、 はに対して未定義であり、の場合は が未定義であることを理解してください。上の同値関係を次のように定義します。 に対してが成り立つのは、 で始まり で終わるおよび関数の 0 回以上の適用のシーケンスが存在する場合のみです。 ゼロ演算のシーケンスが許されることで、の反射性が説明されます。の文字列への任意の有限シーケンスの適用は、 の有限シーケンスの適用で元に戻すことができるという観察から、対称性がわかります。推移性は定義から明らかです。 ${\displaystyle \operatorname {insert} (u,j)}$ ${\displaystyle j>|u|}$ ${\displaystyle \operatorname {delete} (u,j)}$ ${\displaystyle j>|u|-2}$ ${\displaystyle R}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle a,b\in \Sigma ^{*}}$ ${\displaystyle (a,b)\in R}$ ${\displaystyle \operatorname {insert} }$ ${\displaystyle \operatorname {delete} }$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle R}$ ${\displaystyle \operatorname {insert} }$ ${\displaystyle \operatorname {delete} }$

同値関係は言語を同値類に分割します。空文字列を とすると、同値類に対応する言語はDyck 言語と呼ばれます。 ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \epsilon }$ ${\displaystyle \operatorname {Cl} (\epsilon )}$

一般化

型付きDyck言語

Dyck言語には複数の区切り文字を持つバリエーションも存在します。例えば、アルファベットのDyck-2では「(」、「)」、「[」、「]」が使われます。このような言語の単語は、すべての区切り文字が適切に括弧で囲まれています。つまり、単語を左から右に読み、すべての開始区切り文字をスタックにプッシュし、終了区切り文字に達したら、対応する開始区切り文字をスタックの上からポップできる必要があります。（上記のカウントアルゴリズムは一般化できません。）例えば、以下はDyck-3の有効な文です（対応する区切り文字は同じ色で表示されます） 。

 （[ [ ] { } ] （ ） { ） }） [ ] 

有限深度

ダイク言語の文は、入れ子になった括弧の階層を上下に移動する様子として捉えることができます。ダイク文を読み進めていくと、開き括弧ごとに入れ子の深さが1ずつ増加し、閉じ括弧ごとに1ずつ減少していきます。文の深さとは、その文の中で到達できる最大の深さのことです。

たとえば、次の文に各ステップの深さを注釈付けできます。

0 ( 1 [ 2 [ 3 ] 2 { 3 } 2 ] 1 ( 2 ) 1 { 2 ( 3 ) 2 } 1 ) 0 [ 1 ] 0

文全体の深さは 3 です。

Dyck-(k, m)を、k種類の括弧と最大深度mを持つ言語と定義する。これは、リカレントニューラルネットワークの形式理論に応用されている。^[1]

プロパティ

• Dyck 言語は連結演算に関して閉じています。
• を連接のもとで代数的モノイドとして扱うと、モノイド構造が商に転移し、結果としてDyck言語 の構文的モノイドが得られることがわかる。このクラスは と表記する。 ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \Sigma ^{*}/R}$ ${\displaystyle \operatorname {Cl} (\epsilon )}$ ${\displaystyle 1}$
• Dyck 言語の構文モノイドは可換ではありません。 ${\displaystyle u=\operatorname {Cl} ([)}$ ${\displaystyle v=\operatorname {Cl} (])}$ ${\displaystyle uv=\operatorname {Cl} ([])=1\neq \operatorname {Cl} (][)=vu}$
• 上記の表記法では、と のどちらも では逆変換できません。 ${\displaystyle uv=1}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle \Sigma ^{*}/R}$
• Dyck 言語の統語的モノイドは、上で説明したおよびの特性により、双巡回半群と同型です。 ${\displaystyle \operatorname {Cl} ([)}$ ${\displaystyle \operatorname {Cl} (])}$
• チョムスキー＝シュッツェンベルガーの表現定理によれば、任意の文脈自由言語は、ある正規言語とディック言語との1種類以上の括弧対上の交差の準同型像である。 ^[2]
• 2つの異なる種類の括弧を持つDyck言語は複雑性クラス で認識できます。^[3] ${\displaystyle TC^{0}}$
• ちょうどn組の括弧とk組の最も内側の括弧 (つまり、部分文字列)を持つ異なる Dyck 語の数は、ナラヤナ数です。 ${\displaystyle [\ ]}$ ${\displaystyle \operatorname {N} (n,k)}$
• ちょうどn組の括弧を持つ異なるダイク語の数は、n番目のカタロニア数です。n 組の括弧を 持つ単語のダイク言語は、前のポイントで定義したように、最も内側の括弧がk組のn組の括弧を持つ単語のダイク言語の、すべての可能なkの和集合に等しいことに注意してください。kは0 からnまでの範囲にあるため、次の等式が得られ、これは確かに成り立ちます。 ${\displaystyle C_{n}}$

${\displaystyle C_{n}=\sum _{k=1}^{n}\operatorname {N} (n,k)}$

例

長さ8の14個のDyck語の格子 - [と]は上下に解釈される

Dyck言語 において同値関係を定義できます。 が成り立つのは、 が成り立つ場合、すなわち とが同じ長さである場合に限ります。この関係はDyck言語を分割します。が成り立つのは、 が成り立つ場合です。が奇数の場合、 は空であることに注意してください。 ${\displaystyle L}$ ${\displaystyle {\mathcal {D}}}$ ${\displaystyle u,v\in {\mathcal {D}}}$ ${\displaystyle (u,v)\in L}$ ${\displaystyle |u|=|v|}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle {\mathcal {D}}/L=\{{\mathcal {D}}_{0},{\mathcal {D}}_{1},\ldots \}}$ ${\displaystyle {\mathcal {D}}={\mathcal {D}}_{0}\cup {\mathcal {D}}_{2}\cup {\mathcal {D}}_{4}\cup \ldots =\bigcup _{n=0}^{\infty }{\mathcal {D}}_{n}}$ ${\displaystyle {\mathcal {D}}_{n}=\{u\in {\mathcal {D}}\mid |u|=n\}}$ ${\displaystyle {\mathcal {D}}_{n}}$ ${\displaystyle n}$

長さ の Dyck ワードを導入したので、それらに関係を導入できます。任意のに対して の関係を定義します。 が成り立つのは、一連の適切な swapによってから に到達できる場合のみです。ワード内の適切な swap は、'][' を '[]' と交換します。各 に対して、関係により半順序集合が作られます。関係が反射的であるのは、空の適切な swap シーケンスが になるためです。 に になる適切な swap シーケンスを、にになる適切な swap シーケンスと連結して に になるシーケンスを形成できるため、推移性が得られます。 が反対称でもあることを確認するために、 のすべてのプレフィックスの合計として定義される補助関数を導入します。 ${\displaystyle n}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle S_{n}}$ ${\displaystyle {\mathcal {D}}_{n}}$ ${\displaystyle u,v\in {\mathcal {D}}_{n}}$ ${\displaystyle (u,v)\in S_{n}}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle u\in {\mathcal {D}}_{n}}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle S_{n}}$ ${\displaystyle {\mathcal {D}}_{n}}$ ${\displaystyle S_{n}}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle u}$ ${\displaystyle w}$ ${\displaystyle S_{n}}$ ${\displaystyle \sigma _{n}:{\mathcal {D}}_{n}\rightarrow \mathbb {N} }$ ${\displaystyle v}$ ${\displaystyle u}$

${\displaystyle \sigma _{n}(u)=\sum _{vw=u}{\Big (}({\text{count of ['s in }}v)-({\text{count of ]'s in }}v){\Big )}}$

次の表は、適切なスワップに関して が厳密に単調であることを示しています。 ${\displaystyle \sigma _{n}}$

厳密な単調性 ${\displaystyle \sigma _{n}}$

の部分和 ${\displaystyle \sigma _{n}(u)}$	${\displaystyle P}$	${\displaystyle P-1}$	${\displaystyle P}$	${\displaystyle Q}$
${\displaystyle u}$	${\displaystyle \ldots }$	]	[	${\displaystyle \ldots }$
${\displaystyle u'}$	${\displaystyle \ldots }$	[	]	${\displaystyle \ldots }$
の部分和 ${\displaystyle \sigma _{n}(u')}$	${\displaystyle P}$	${\displaystyle P+1}$	${\displaystyle P}$	${\displaystyle Q}$
部分和の差	0	2	0	0

したがって、を に取り込む適切なスワップが存在する場合、 が成り立ちます。ここで、との両方が であると仮定すると、を に取り込むような、またその逆の、空でない適切なスワップの列が存在します。しかし、 の場合、 は無意味です。したがって、と の両方が に含まれる場合、 が成り立ち、したがって は反対称です。 ${\displaystyle \sigma _{n}(u')-\sigma _{n}(u)=2>0}$ ${\displaystyle \sigma _{n}(u)<\sigma _{n}(u')}$ ${\displaystyle u}$ ${\displaystyle u'}$ ${\displaystyle (u,v),(v,u)\in S_{n}}$ ${\displaystyle u\neq v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle \sigma _{n}(u)<\sigma _{n}(v)<\sigma _{n}(u)}$ ${\displaystyle (u,v)}$ ${\displaystyle (v,u)}$ ${\displaystyle S_{n}}$ ${\displaystyle u=v}$ ${\displaystyle S_{n}}$

[ を上昇、 ] を下降と解釈した場合、部分順序集合は導入部に添付された図に示されています。 ${\displaystyle D_{8}}$

参照

• ディック合同
• 格子単語

注記

1. Hewitt, John; Hahn, Michael; Ganguli, Surya; Liang, Percy; Manning, Christopher D. (2020-10-15). 「RNNは最適なメモリを備えた境界付き階層言語を生成できる」arXiv : 2010.07515 [cs.CL].
2. カンビテス、代数学コミュニケーション第37巻第1号（2009年）193-208
3. バリントンとコーベット、情報処理レター32（1989）251-256

参考文献

• PlanetMathの Dyck 言語。
• チョムスキー・シュッツェンベルガー定理の証明
• Dyckの言葉に関するAMSブログ記事

Retrieved from "https://en.wikipedia.org/w/index.php?title=Dyck_language&oldid=1282954608"