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