正規射の概念

クリーネ圏やコォゼン圏に関しては、正規表現と正規射（regular morphism）という概念を相対的にに定義できる。

一番分かりやすいのはコォゼン圏だから、Cはコォゼン圏だとしよう。A⊆Cを任意の部分グラフとする。正確には、Cをプレ圏とみなして、部分プレ圏がA。Aから形式的に生成された自由コォゼン圏をFK(A)とする。FK(A)を作るには、プレ圏Aからの自由生成アルゴリズムを使う。FK(A)を作るさいに出てくる形式的な表現が正規表現。

正規表現は、FK(A)の射に対応する。正規表現が同値だとは、同じ射に対応すること。FK(A)は自由コォゼン圏なので、自然な関手KF(A)→Cがある。この関手の像に入る射は正規射と呼び、正規射の全体をReg(A, C)とする。Reg(A, C)はCの部分コォゼン圏となっている。

Cとして、アルファベットΣ上のすべての言語を係数とする行列からなる初歩的圏、Aとして、単元言語の集合をとると、古典的な正規言語の概念が得られる。正規射は、正規言語を係数とする行列で与えられる。特に1×1行列は正規言語そのものである。