ディック言語

ディック言語（ディックげんご、英: Dyck language）とは形式言語理論分野、数学分野および言語学分野において研究されている形式言語の一種である。この言語は開括弧（[）と閉括弧（]）から構成されており、どの閉括弧についても、それ以前に出現した開括弧のいずれかと対応する。さらに文字列の終端に達した際には開括弧と閉括弧の個数が一致している。前半部分の説明は、文字列中のどの括弧についても、文字列の先頭からその括弧までたどった際に存在する開括弧の数がそれまでたどった際に存在する閉括弧の数と等しいかそれよりも多くなっていると言い換えることもできる。つまり、対応する括弧を対として考えるとどの対もその外にある括弧の対に必ず内包されており、この性質は様々な表現の構文解析等において重要である。名前の由来はドイツの数学者、ヴァルター・フォン・ダイクである。

[と]を用いた長さ8の語を図示した束．[を上への移動，]を下への移動して解釈する．

定義

アルファベット集合 Σ を Σ = { [, ] }とし，そのクリーネ閉包を Σ^* で表す．Σ^* 内の任意の要素 u ∈ Σ^* について，その長さを |u| で表し，2つの 部分関数 insert : Σ^* × (N ∪ {0}) → Σ^* と delete : Σ^∗ × N → Σ^∗ を以下のように定義する．

insert(u, j) = u の j 番目の位置に "[]" を挿入する

delete(u, j) = u の j 番目の位置から "[]" を削除する

自然に、insert(u, j) はj > |u| の場合において、そしてdelete(u, j)は j > |u| − 2 の場合において、定義されない。また、 Σ^∗ 上の同値関係 R を

ある要素 a, b ∈ Σ^∗ について (a, b) ∈ Rであるための必要十分条件は有限回の insert または delete 操作において a から b が生成されることである。なお、この有限回の操作には、0回の操作も含む。

と定義する。0回の操作が許されることでRにおいて反射律が明らかに成り立つ。また、insertを有限回適用する操作はdeleteを有限回適用することによって打ち消すことができるため，同時に 対称律 を満たす同値関係となる。さらに、推移律が成り立つことも明らかである。ここで、このように定義された同値関係によって構成された同値類のうち、ある元 xが含まれる同値類全体をCL(x)で表すとする。このときディック言語は、空文字列をεで表すとしたときに同値類 CL(ε) に対応する言語と定義づけられる。

主な性質

• 文字列結合についてディック言語は閉じている。

関連項目

• カタラン数