ディック言語

ディック言語（ディックげんご）とは形式言語理論分野、数学分野および言語学分野において研究されている形式言語の一種である。この言語は開括弧（"["）と閉括弧（"]"）から構成されており、どの閉括弧についても、それ以前に出現した開括弧のいずれかと対応する。さらに文字列の終端に達した際には開括弧と閉括弧の個数が一致している。前半部分の説明は、文字列中のどの括弧についても、文字列の先頭からその括弧までたどった際に存在する開括弧の数がそれまでたどった際に存在する閉括弧の数と等しいかそれよりも多くなっていると言い換えることもできる。つまり、対応する括弧を対として考えるとどの対もその外にある括弧の対に必ず内包されており、この性質は様々な表現の構文解析等において重要である。名前の由来はドイツの数学者、である。
定義.
アルファベット集合 Σ を Σ = { [, ] }とし，そのクリーネ閉包を Σ* で表す．Σ* 内の任意の要素 "u" ∈ Σ* について，その長さを |"u"| で表し，2つの 部分関数 "insert" : Σ* × (N ∪ {0}) → Σ* と "delete" : Σ∗ × N → Σ∗ を以下のように定義する．
自然に、"insert"("u", "j") は"j" > |"u"| の場合において、そして"delete"("u", "j")は "j" > |"u"| − 2 の場合において、定義されない。また、 Σ∗ 上の同値関係 "R" を
と定義する。0回の操作が許されることで"R"において反射律が明らかに成り立つ。また、"insert"を有限回適用する操作は"delete"を有限回適用することによって打ち消すことができるため，同時に 対称律 を満たす同値関係となる。さらに、推移律が成り立つことも明らかである。ここで、このように定義された同値関係によって構成された同値類のうち、ある元 "x"が含まれる同値類全体をCL(x)で表すとする。このときディック言語は、空文字列をεで表すとしたときに同値類 CL(ε) に対応する言語と定義づけられる。