形式言語理論における状態のリフト

Σをアルファベットとして、Σで生成された自由モノイドを考えると、これは語（列）の全体。M = (Σの列の全体）とする。モノイドMの表現とは、集合Xに対するM作用だとする。End(X)にMが表現される。Xは、まー表現空間といっていいだろう。

Mの表現として、X=Mとしての右移動、左移動がある。これでとりあえず、表現の存在が示せる。次に、モノイド表現があるとき、状態のリフトをして、状態関数の空間を新しい状態空間に取れる。これは、モノイド作用を「決定性→非決定性」にしたことと同じ。

ここで、a∈Σにたいして、aが定義する作用素a_*がどんなものかというと、

• Σ上の言語Aに対して、a_*A = {aα | α∈A }

状態をリフトしてうれしいのは、a^*という作用素が次のように定義できること。

• Σ上の言語Bに対して、a^*B = {β | aβ∈B }

次が成立する。（1は恒等作用素）

• a^*・a_* = 1
• a_*・a^* ⊆ 1

この関係が、生成と認識の基本事項だと思う。