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

アルファベット集合 Σ を Σ = { [, ] }とし，そのクリーネ閉包を Σ* で表す．Σ* 内の任意の要素 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(ε) に対応する言語と定義づけられる。
主な性質

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

関連項目

カタラン数
.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox{font-size:90%}.mw-parser-output .asbox-note{font-size:90%}.mw-parser-output .asbox .navbar{position:absolute;top:-0.90em;right:1em;display:none}

この項目は、数理論理学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。
.mw-parser-output .hlist ul,.mw-parser-output .hlist ol{padding-left:0}.mw-parser-output .hlist li,.mw-parser-output .hlist dd,.mw-parser-output .hlist dt{margin-right:0;display:inline-block;white-space:nowrap}.mw-parser-output .hlist dt:after,.mw-parser-output .hlist dd:after,.mw-parser-output .hlist li:after{white-space:normal}.mw-parser-output .hlist li:after,.mw-parser-output .hlist dd:after{content:" ・\a0 ";font-weight:bold}.mw-parser-output .hlist dt:after{content:": "}.mw-parser-output .hlist-pipe dd:after,.mw-parser-output .hlist-pipe li:after{content:" |\a0 ";font-weight:normal}.mw-parser-output .hlist-hyphen dd:after,.mw-parser-output .hlist-hyphen li:after{content:" -\a0 ";font-weight:normal}.mw-parser-output .hlist-comma dd:after,.mw-parser-output .hlist-comma li:after{content:"、";font-weight:normal}.mw-parser-output .hlist-slash dd:after,.mw-parser-output .hlist-slash li:after{content:" /\a0 ";font-weight:normal}.mw-parser-output .hlist dd:last-child:after,.mw-parser-output .hlist dt:last-child:after,.mw-parser-output .hlist li:last-child:after{content:none}.mw-parser-output .hlist dd dd:first-child:before,.mw-parser-output .hlist dd dt:first-child:before,.mw-parser-output .hlist dd li:first-child:before,.mw-parser-output .hlist dt dd:first-child:before,.mw-parser-output .hlist dt dt:first-child:before,.mw-parser-output .hlist dt li:first-child:before,.mw-parser-output .hlist li dd:first-child:before,.mw-parser-output .hlist li dt:first-child:before,.mw-parser-output .hlist li li:first-child:before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child:after,.mw-parser-output .hlist dd dt:last-child:after,.mw-parser-output .hlist dd li:last-child:after,.mw-parser-output .hlist dt dd:last-child:after,.mw-parser-output .hlist dt dt:last-child:after,.mw-parser-output .hlist dt li:last-child:after,.mw-parser-output .hlist li dd:last-child:after,.mw-parser-output .hlist li dt:last-child:after,.mw-parser-output .hlist li li:last-child:after{content:")\a0 ";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li:before{content:" "counter(listitem)" ";white-space:nowrap}.mw-parser-output .hlist dd ol>li:first-child:before,.mw-parser-output .hlist dt ol>li:first-child:before,.mw-parser-output .hlist li ol>li:first-child:before{content:" ("counter(listitem)" "}.mw-parser-output .navbar{display:inline;font-size:75%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}.mw-parser-output .infobox .navbar{font-size:88%}.mw-parser-output .navbox .navbar{display:block;font-size:88%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}

表示

編集