ダイク言語

コンピュータサイエンス、数学、言語学の形式言語の理論では、ダイク語はバランスの取れた括弧の文字列です。ダイク語の集合はダイク言語を形成します。最も単純な Dyck-1 は、( と ) のように、対応する括弧を 2 つだけ使用します。

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

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

${\displaystyle \{u\in \Sigma ^{*}\vert {\text{ }}u{\text{ のすべての接頭辞には [ の数より多くの ] が含まれず}}{\text{ }}u{\text{ 内の [ の数は ] の数に等しい}}\}}.}$

状況によっては、文脈自由文法を介して 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 {挿入} :\Sigma ^{*}\times \mathbb {N} \rightarrow \Sigma ^{*}}$${\displaystyle \operatorname {delete} :\Sigma ^{*}\times \mathbb {N} \rightarrow \Sigma ^{*}}$

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

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

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

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

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

たとえば、次の文は Dyck-3 では有効です。

( [ [ ] { } ] ( ) { ( ) } ) [ ]

Dyck 言語の文は、ネストされた括弧のレベルを上下するものとして表すことができます。Dyck 文を読み進めていくと、各開始括弧によってネストの深さが 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組の括弧を持つ異なる Dyck 語の数は、n番目のカタロニア数 です。n組の括弧を持つ語の Dyck 言語は、前のポイントで定義したように、最も内側のk 組の括弧を持つn組の括弧を持つ語の Dyck 言語の、すべての可能なkについての和集合に等しいことに注意してください。k は0 からnまでの範囲にあるため、次の等式が得られ、これは実際に当てはまります。${\displaystyle C_{n}}$

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

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 のシーケンスと連結して に かかるシーケンスを形成できるため、推移性が得られます。も反対称であることを確認するために、 のすべてのプレフィックスの合計として定義される補助関数を導入します。 ${\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}(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}}$

• ディック合同
• 格子ワード

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