形式言語理論は、かなりの程度、代数的に定式化できます。例えば、形式言語の全体は順序半環、オートマトンはその順序半環を係数とする正方行列だと思えます。オートマトンの初期状態と終状態、オートマトンのあいだの模倣(simulation)関係なども行列により表現できます。 ここでは、できるだけ手短に形式言語理論のための代数、特に半環係数行列の概念を説明します。形式言語とオートマトンの基礎事項についても概要を述べますが、とてもラフな記述なので、他の資料や教科書で予備知識は仕入れておいたほうがいいでしょう。図を多用して幾何的・物理的な比喩を使うと分かりやすくなるとは思うのですが、今回は絵は描きませんでした。絵による説明はまたの機会に。 目標はオートマトンと模倣の圏を作ることです。オートマトンは代数的には正方行列となります。関係圏Rel(の部分圏)をインデキシング圏とするインデックス付き圏を作り、そのグ