正規表現と正規言語の対応関係を拡張／一般化するために、正規構造という 構文／意味システムを導入する。正規構造とは、基本的な代数系（ただし、特 に法則を要求しない）をベースに、最小不動点を意味する項を導入して代数系 を拡張するメカニズムの定式化である。
この記事では、正規性（regularity）概念を一般的に定式化する1つの試みを 示す。同じ話題について、既に記事「『正規（regular）』 とは何なんだ」で論じている。記事「『正規（regular）』とは何なんだ」 では、「正規性とは、再帰代入系で定義される」ことを一応の結論としている。 が、本記事では、正規性の別の定式化を提示する。
この記事で採用する道具立て／枠組みは正規構造（regular structure）と呼 ぶことにする。正規構造は正規代数（regular algebra）の変種であり、正規表現と 正規言語の対応をストレートに一般化することを狙っている。正規構造と再帰 代入系は最終的には統合されるべきものだが、複数の入り口を作っておくこと は（おそらく）無駄ではないだろう。
この記事の最初のほうで、列言語に対する正規表現とその解釈（正規表現の 意味論）を復習する。それから、「正規表現⇔正規言語」対応のエッセンシャ ルな部分を抽出し、一般化することにより正規構造を導入する。 また、正規構造で採用しているアプローチが伝統的な手法であることを指摘す るために、（記事の何カ所かで）数系の拡大との対比も行う。
参考文献として、形式言語理論の教科書は、いつものとおり （「形式言語理論への疑問など」の第2節も参 照）次の2冊を挙げておく。
正規代数（正則代数）については、次が代表的な文献のようだ。
列言語における正規性の概念は、非常にシッカリとした自然な（とても人為 的とは思えない）ものである。正規表現、線形文法、オートマトン、Kleene代 数など、さまざまな定式化により正規性を定義できる。
しかし、記事「『正規（regular）』とは何なんだ」 の第5節でも述べたように、列言語のときは、どうも話がうまく行き過ぎて いる。列以外のデータ構造に対して、このような万全の整合性／精緻性を望む のは虫が良すぎる、というのが僕の印象だ。
記事「『正規（regular）』とは何なんだ」では、一般的な正規性を定義する 手段として再帰代入系（「再帰代入 系 1」、「再帰代入系 2」参 照）を想定している。再帰代入系は、モジュール化された （modularized）BNF規則とも言える系で、（強いて言えばだが）線形文法によ る正規性の定義を一般化したようなものである。有限から無限を生み出すメカ ニズムは再帰部（再帰方程式、不動点方程式）が担う。正規表現やKleene代数 におけるスター演算子のようなものはない（より正確に言えば、いつでもある とは限らない）し、スッキリとした代数構造も期待してない。
それに対して、再帰構造はより代数的である（スッキリとはしてないが）。有限から無限を生み出す演算、 つまりKleeneスターの一般化は必要なら明示的に導入する。新しい演算を導入して、 それによって代数系を拡張するという方法を採用するわけだ。おおざっぱに言えば、 再帰構造とは、基礎となる演算を備えた代数系を、再帰方程式により定義され る演算を付け加えて拡大したものである。
記事「属性のための正規表現」の第1節で述 べたように、正規表現にはいくつかの変種がある。ここでは、構文的演算子と して、「,」「|」「*」の3つを採用し、他に定数EMPTYを使う。
以下で使う記法は次の表にまとめてある。また、必要があれば、 記事「『正規（regular）』とは何なんだ」の第2節 や、そこから参照されている関連記事（の当該部分）を読むとよいだろう。
| 慣例的記号 | 関数名/引数個数 | 理論的な記法 | 言語（集合）における概念 |
|---|---|---|---|
| , | concat/2 | ・ | 連接 |
| ｜ | choice/2 | + | 合併 |
| * | repeat/1 | * | Kleeneスター |
| EMPTY | empty/0 | 1 | 空列からなる単元言語 |
列言語の‘正規表現’（regular expression）を正式に定義しておこう。 正規表現の帰納的（inductive）な定義は、 「順序言語」の第5節にあるが、ここでも繰り返しておく。Σはアルファベッ ト（与えられた基本記号の集合）とする。
記事「順序言語」では、EMPTYを「1」で表しており、連接に「;」を使ってい る。また、記事「順序言語」では空集合を表す定数「0」も入っているが、と りあえずなくても不便はないので、ここでは入れてない(*注1)。
結局、後で必要になってコソッと入れたりしているのだけどね。
上の正規表現の定義は、慣例的記号「,」「|」「*」を使って述べたが、対応 する関数記法を使えば、次のような定義となる。
この定義と、記事「『形式的』とは何だろう」 第4節の“項の定義”を比べてみてほしい。帰納的な定義方法はまったく同 じである。つまり、正規表現とは、形式的体系（formal system）における項 （term）の特殊事例なのである。
形式的体系の項については、記 事「再帰代入系 1」の第4節で述べているが、同じ事を繰り返えせば： 変 数記号全体の集合Kと、関数記号の集合達F0, F1, F2, ... （Fiは引 数の個数がiの関数記号）が与えられたとき、‘項’（term）は次のように帰 納的に定義される。
上の定義で得られる項の全体をTermF(K)と書く。変数をX（X⊆K）に限定し た項の全体はTermF(X)と書く。Fが周知ならTermF(X)をTerm(X)とも書き、 Fを強調したいならTermF(X)をTerm(F, X)とかTerm(F)(X)と書くこともある (*注2)。
一般的に、2変数のナニカf(x, y)があるとき、xはとりあえず止めて（固定し て）、yの変動を考えたいときに fa(y)のような書き方をする。また、xに対 する値f(x)が関数（fは関数値の関数）になっていて、その関数に変数yを入れ た形がf(x)(y)となる。f(x, y)をf(x)(y)の形にすることはカリー化と呼ぶ。 カリー（Curry）は人名（1900-1982）、ちなみにCurryのファーストネームはHaskell。
ここでは、正規表現の直接的な“意味”として正規言語を定義しよう。
Σのメンバーから構成される列の全体をSeq(Σ)とする。通常、 Σ上の正規表現は、Σ上の言語（つまり、Seq(Σ)の部分集合）として解釈さ れる。これについては、記事「『正規（regular）』 とは何なんだ」のノート「正規表現の標準的解釈」に記している。
標準的解釈においては、Σのメンバーaの意味は{"a"}という単元言語である。 だが、Σのメンバーに自由に意味を与えてもよい。例えば、 「順序言語」の第5節では、Σのメンバーa の意味は、[a]↓によって示される下方閉な集合である。一方、 記事「属性のための正規表現」の第7節では、Σ のメンバーaの意味は、適当な集合の集合 B(a)∈Pow(Pow(X))としている。
記事により記号法がマチマチだな。a∈Σに対する長さ1の列が"a"だったり [a]だったり、連接が「,」だったり「;」だったり。そのうち整理したいとも 思うが、この程度のゆれ／食い違いはしかたのないことかも知れない。
一般的には、Σ上の正規表現は、Σとは異なるかもしれないアルファベット Π上の言語として解釈してよい。以下に、そのような解釈の定義を記す。正規 表現rの意味をM(r)とする。先に示した正規表現の帰納的定義に従ってM(r)を 定義する(*注3)。
この記事の後のほうでは、丸括弧の入れ子を嫌ってM[r]としている。
この定義では、「M(a)はaごとに自由に割り当ててよい」となっている。つま り、ΣからPow(Seq(Π))への写像（a∈Σに、Seq(Π）の部分集合を割り当て る対応）を、前もって勝手に決めておいてよいことになる。いま、Σ→ Pow(Seq(Π)) の写像をvとして、これを‘付値’（valuation）と呼ぶ(*注4)。 付値vを与えれば、意味写像Mは自動的に決まってしまう。念のため、vから決 まるMの定義を繰り返しておけば：
付値は、環境（environment）とか文脈（context）と呼ばれることもある。
正規表現と付値vにより、アルファベットΠ上の（vにより決まる）‘正規言 語’を定義することができる。
通常、空言語{}も正規言語に含める。
この条項はしばしば省略されるが、必要なものである。 後で出てくるKleene代数の言葉を用いれば、正規表現の全体は、v(a)達を含む 最小の部分Kleene代数である。その最小性を主張しているのが、この条項であ る。
付値vによりv(a)の形に書ける言語の全体は、{v(a) : a∈Σ}という言語族と みなせる。付値と無関係に、単に言語族{Bi : i∈I}が与えられた場合でも、 {Bi : i∈I}に相対的に正規言語を定義できる。
この節でKleene代数に関して急ぎ足でまとめる。代数的な内容であるから、 あまり詳細は気にしないで、ザッと目を通したら次節に移ったほうがよい。
今までの流れを振り返れば、正規表現を解釈するためには、定数EMPTYに対応 する特定対象と、3つの演算記号「・」、「∪」、「*」に対応する（ホントの） 演算を備えているような代数系(*注7)があればよいことがわかる。「・」、 「∪」、「*」が言語の連接、合併、Kleeneスターを意味する必要はない。
代数系／代数構造の正式な定義は後で与える。
一般に、正規表現を解釈できるような代数系を‘Kleene代数’と呼ぶ。 Kleene代数とは、次のような条件を満たす構造を備えた集合Kである(*注8)。
アッ、記号Kは、変数集合の全体を表すのに使っていた。文字Kを選んだ理由 が「他の目的で使う予定がないから」だったが、Kleene代数ならKを使いたい よね、やっぱり。文字Kが何を表すかは文脈で判断してください。
演算*以外に関する規則を等式で書き下せば次のとおり（ただし、・は省略し た書き方をする）。
通常は、0∈Kの存在と 0 + a = a + 0 = a も仮定する。（0は＋の単位元だ が、それより、順序に関する最小元として必要とされることがある。）
Kleene代数において、a≦bをa + b = b のことだとして定義すると、次が成 立する(*注9)。
可換、ベキ等、結合的な演算+が定義されていれば、a≦b ⇔ a + b = b と いう定義は有効である。
さて、演算*は、次の等式群を満たすとする。
以上がKleene代数の定義（公理群）である。
通常の列言語の全体Pow(Seq(Σ))はもちろんKleene代数だが、 記事「順序言語」に出現した、下方閉集合の全 体PowLC(Seq(Σ))もKleene代数になる。記事 「属性のための正規表現」に出現した、集合言語の全体Pow(Pow(Σ))もま たKleene代数である。だから、PowLC(Seq(Σ))もPow(Pow(Σ))も正規表現 の解釈の場となったのである。
KがKleene代数のとき、L⊆Kが、1, 0∈Lであり、しかも+、・、*で閉じてい れば、Kの‘部分Kleene代数’という。特に、任意のS⊆Kに対してSを含む最小 の部分Kleene代数が存在する。これは、（Kにおいて）‘Sから生成された部分 Kleene代数’と呼ぶ。言語族{Bi : i∈I}に対して定義された相対的正規言語の全 体は、実はPow(Seq(Σ))において{Bi : i∈I}から生成された部分Kleene代 数である。
/* ここから書き足した部分 */
Kleene代数には、3つの演算（演算“記号”ではない）が備わっているが、ス ター演算*は忘れて、足し算+と掛け算・だけを見てみよう。足し算+と掛け算・ が満たす法則を再び述べてみる。
掛け算の可換性（ab = ba）が仮定されていない点と、足し算に関する「a + a = a」 （ベキ等律という）は異質だが、それ以外は、小学校で習った算数と 変わりはない。つまり、足し算+と掛け算・を考えている限りは、初等代数的 あるいは算術的なレベルにとどまり、再帰性や無限性が入り込む余地がない。
Kleene代数の自明でない特徴はスター演算*に集約されている。では、a∈Kに 対するa*は一体何なのかというと、方程式 x = 1 + ax の解である。実際、 xにa* を代入した形 a* = 1 + aa* はKleene代数の公理の一部である。
ただし、x = 1 + ax の解は存在しても一意的とは限らない。となると、a* を「x = 1 + ax の解」として一意的に特徴付けることができなくなる。しか し実際には、「x = 1 + ax の最小解」であることが、残りの公理（ab≦b ならば a*b ≦ b、ba≦b ならば ba* ≦ b）から保証される。このことに ついては、文献[守屋]の2.5.3節に少し一般化された次の形で証明されている。
つまり、Kleene代数は、足し算+と掛け算・を備えた初等的代数系に対して、 方程式 x = 1 + ax の最小解としてa* を付け加えたものだといえる。
このように、既存の代数系に方程式の解を付け加えることは、歴史的にも教 育課程でも頻繁に延々と繰り返された手法である。たとえば、ゼロの導入では、 任意のaに対して方程式 x + a = a を満たすようなx、つまりこの方程式の解 としてゼロが定義された。さらに方程式 x + a = 0 の解として-aが導入され る。平方根や虚数の導入、それに伴う数系の拡大も事情は同じである。 このことは、第10、11, 12節でもっと詳しく述べる。
Kleeneスターa*は、方程式 x = 1 + ax の最小解なのだが、通常 1 + a + a2 + ... という無限級数の表示を持つ。これは次のような事情である。
まず、x = 0 が解になっているかどうかを見ると、0 = 1 が成立していれば OKだが、それ以外なら0は解ではない。そこで次に、1 + axのxに0を代入した 値1を解の候補と考える。 1 = 1 + a が成立していればOKだが、一般にはそうではない。では、1 + a1 = 1 + a で はどうか？ 1 + a = 1 + a(1 + a) が成立していればよいが…… この繰り返 しは、 x0 = 0 （0は最小値）から初めて、xn+1 = 1 + axn という系列を順 次作っていることになる。
このような手順で、0, 1, 1 + a, 1 + a + a2 のような近似系列を作れる。 これが実際の解に収束することは別に合理化する必要があるが、適当な条件下 では、この近似系列の極限が実際の解を与えることが示せる（各種の不動点定 理）。これを根拠に、 a* = 1 + a + a2 + ... に意味を持たせることができる。
方程式の解を数系に付け加えることにより、“本来存在するはずのなかった 数”を既存の数系に組み入れることができる。そのような仮想的な対象（新し い数）も含めることにより、より計算が楽になり、より豊かな記述能力を手に 入れてきたわけだ。
後で定義する正規構造は、Kleene代数の概念のなかで、「基底となる初等的 代数に、方程式（再帰方程式、不動点方程式）の最小解を付け加える」という 構成法に注目した一般化である。
一般の正規構造を定義する前に、Kleene代数の条件を弱めた‘Kleene構造’ からはじめよう。Kleene構造は正規構造の特別な事例となっている。
Kleene代数を定義するときに使った定数と演算記号を再び採用する。ただし、 以下では関数記法を用いることにして、F0 = {empty}、F1 = {repeat}、 F2 = {concat, choice}、その他のFi = {} とする。
さらに集合Σを適当に選んでTermF(Σ)を考える。Σはアルファベットだが、 （定数として使うのではなくて）項を構成する変数集合として使う。‘正規項’ （regular term）という概念によりTermF(Σ)を拡張する。 正規項は正規表現の形式化されたバージョンである。正規項の帰納的定義は次 のとおり。ただし、zはΣには含まれない記号だとする。
μz.[choice(empty, concat(t, z))]の形の正規項を‘μ（ミュー）正規項’ （mu regular term）、または単に‘μ（ミュー）項’と呼ぶ。 μz.[choice(empty, concat(t, z))]と書くと複雑そうだが、もっと簡略に書 けばμz.[1 + tz]である。
μ項に出現する変数記号zは（μオペレータの）‘束縛変数’と呼ぶが、Σの メンバーでなければどんな記号でもよい。また、束縛変数は必ず1つ出現する だけでまぎれる心配はまったくないから、μの直後のzは書かずに μ[choice(empty, concat(t, z))]でもよい。μ[choice(empty, concat(t, z))]のなかで変動するのはtだけだから、さらにμ(t) のように略記してしまっ てもさしつかえない。
略記μ(t)を採用して正規項を定義してもよい。 ただし、省略形μ(t)を元の 形に戻す必要はある（後で、一般の正規構造の定義を見ればわかるだろう）。
略記μ(t)を採用するかどうかは本質的な問題ではない。略記を使っても使わ なくても、上のようにして定義された正規項の全体をRegTermF(Σ)とする。 μ(t)をt*のことだと思えば、RegTermF(Σ)は普通の正規表現そのものであ ることを各自確認してほしい。
以上で、Kleene構造の構文側は定義が終わった。なんのことはない、普通の 正規表現をもって回った言い方で再定義したに過ぎない（という理解で正しい のだ）。
Kleene構造の意味的部分は、集合とその上のホントの演算から構成される。K を集合として、e∈K、単項演算*:K→K、2項演算+:K×K→K、・:K×K→Kが与え られているとする。KはKleeene代数と同じ特殊元と演算を備えているが、 Kleene代数のように等式（演算の法則）を満たすことは要求されていない。た だし、K上には順序≦があるとする。*、+、・は、K上の順序に対して単調写像 になっているとする(*注10)。
x ≦ y ならば f(x) ≦ f(y) のとき単調という。
単調写像であることを仮定しないこともあるが、ここではすべての写像が単 調だとしておく。
前節で定義したRegTermF(Σ）と、いま準備した(K, e, *, +, ・, ≦)を結 びつけよう。まず付値v:Σ→Kを与える（与え方は自由）。付値vに基づいて、 M:RegTermF(Σ）→ Kを次のように定義する。
ここで、M(μ(r))の定義には若干の問題がある。f(x) = e + M(r)・x で定義 されるf: K→Kの最小不動点が存在することが保証されない。 よって、M(μ(r))は未定義になる可能性がある。対処法としては、未定義でも よいとする方法と、ちゃんと定義される場合に限って考える方法がある。ここ では後者の方法を採用する。つまり、f(x) = e + M(r)・x の最小不動点は常 に存在すると仮定する。
さて、結局‘Kleene構造’とは何かと言えば、正規項RegTermF(Σ)の解 釈を与えるシステムである。Kleene代数と異なるのは、計算法則を何も仮定し てないことである。よって、(K, e, *, +, ・, ≦)の演算が a + a = a と か e・a = a などを満たすことは全然保証されない。だから、通常の正規表現 の常識が通用しないかもしれない。
念のため、あらためてKleene構造の構成素を示しておけば、必要な特殊元／ 演算／順序が定義された集合(K, e, *, +, ・, ≦)と、付値v:Σ→Kである。 これが与えられれば、M:RegTermF(Σ) → K は自動的に決まってしまう。
Kleene構造を定義する際に、Kleene代数では要求していた演算の法則（結合 律や分配律など）は捨ててしまった。なぜ、法則を捨てたかというと、一般の データ構造に関して、Kleene代数のような整った法則のセットが見つかること は期待できないからである。もちろん、演算法則を見つけることは重要だし、 それが見つかれば役に立つのも明らかである。しかし、さまざまなデータ構造 に対する“言語”（ツリー言語、レコード言語、マップ言語、バッグ言語、そ の他いろいろ）に対して完全な法則性（公理化）を要求するのは現実的ではな い。演算法則が部分的にでも見つかればラッキーと考えておこう。
このような事情で、代数的な法則性よりはむしろ、再帰方程式の最小解とし て新しいメンバーや演算を導入できる能力に注目する。別な言い方をすれば、 Kleeneスター演算の一般化が厳密に定義できるようなメカニズムを問題にする。 この方針に従って定義される構文／意味システムが正規構造である。
正規構造を定義する際の要点は、正規表現の一般化である正規項をキチンと 定義することと、正規項のなかで特にμ項に対して、最小不動点としての意味 を与えることである。この2点がうまくいけば、他のことは気にしないこ とにしよう。
Kleene構造のときは、F0 = {empty}、F1 = {repeat}、F2 = {concat, choice}、その他のFi = {} という特別な関数記号集合を使ったが、一般の 正規構造では、任意の関数記号集合F = (F0, F1, F2, ...)から出発す る。また、Kleene構造で使った変数集合Σは、もともと言語のアルファベット だったものを変数として“流用”した感じだった(*注11)が、一般の正規構造 では、変数記号集合になんの仮定もしないし、条件も設けない。
これはあくまで「感じ」の問題である。変数の正体が何であるかは、まった く問題ではない。どんなモノであれ、それが置換（substitution, replacement）の対象となるなら、それは変数なのである。
関数集合Fと変数集合Xに対して、項の全体TermF(X)は通常どおりに定義す る。「通常どおり」については、 記事「再帰代入系 1」の第4節や記事「『形式的』 とは何だろう」の前半（第5節まで）を見て欲しい。このTermF(X)をベー スにして、それを拡張することにより正規項（regular term）の 全体RegTermF(X)を定義するが、そのための道具として、再帰テンプレー トというものを導入する。再帰テンプレートは、慣れてしまえば、ごくあり きたりの道具だが、定義だけを見ても意味不明なところがある。節を改めて、 助走としてインフォーマルな説明からはじめよう。
/* ここからさらに書き足した部分 */
前節で、「助走としてインフォーマルな説明」をすると述べた。概念の導入 のさいに、助走路を設けるかどうかは毎度悩む。僕は、気合いが入りすぎてい ると、助走や準備をすっとばしてイキナリ抽象的な概念を持ち出すこともある が、これはよろしくない。が、かといって、長い助走路や補助的概念の説明を “まどろっこいしい”、“迂遠”と感じる人もいるだろう。
この記事に関して言えば、ダラダラと書いていたら、気合いは失せてしまっ た。よって、一気に抽象的な概念を提示する気分がしない。という、まことに 勝手な理由で、ちょっと冗長な説明を挿入することにする。記事が長くなるの は困ったことだが、人によっては、冗長な説明を懇切丁寧と受け取ってくれる かもしれない（って、勝手な言い訳）。
以下に述べるインフォーマルな説明は、第6節「数系の拡大との対比」 の続きのようなものである。正規構造で使われる手法が、お馴染みのもので あることを強調したいのだ。よって、過去を振り返る。過去とは歴史的な過 去でもあるし、個人の過去（小学校から高校あたり）でもある。
小学校から高校あたりで習う数系（自然数、整数、有理数など）は、実数系 の部分系になっている（複素数は例外）(*注12)。Rは実数系（演算や順 序を備えた実数全体のこと）だとして、Rを「世界」として考えよう。 「世界」とは、記号的表現を解釈する普遍的（universal）な場ということで ある。
高校卒業までに、実装の概念をちゃんと理解しているかというと、たぶんそ うではない。だが、ちゃんと理解している必要はない。四則演算と数直線のイ メージがあればそれで十分だと思う。
関数f:R→Rがあるとき、f(x) = 0 となるようなxの全体をfの‘零点集合’と 呼び、Z(f)と書く（Zはzeroに由来）。Z(f)は空かもしれない （例：f(x) = x2 + 1）、無限集合かもしれない（例：f(x) = 0, f(x) = sin x）。Z(f)が空ではなくて、Z(f)から一点（1つの実数）を選び出す方法が あるとき、選び出された実数をτ(f)と書くことにしよう。
「一点を選び出す方法」には、例えば次のようなものがある。
fの零点集合Z(f)は、「方程式f(x) = 0 の解集合」と言い換えても同じであ る。だから、τ(f)の定義の背後には、「関数→方程式→解集合→一点の選択」 という長い手順がある。
ところで、関数fを定義するには、通常は式（形式的体系の用語なら“項”） が使われる。例えば、x2 - 2 という多項式（2次式）が関数を定義する。式 （項）は記号的な存在だから、機能的実体である関数とは違うものである。式 により定義された関数を指示する記法にラムダ記法がある。例えば、x2 - 2 という多項式で定義される関数はλx.(x2 - 2) と書く。（これは内容的な ラムダ記法であり、形式的ラムダ式ではない。）式に登場する変数の名前は問 題にならないので、 λs.(s2 - 2) と λx.(x2 - 2) はまったく同じ関数である。
「式と関数は違います」に対して、「えーっ、関数って式のことじゃないの？」 という反応はけっこうありそうだ。コンピュータ関連業界の人に対してなら、 「ソースコードと実行可能形式は違うでしょ」と言えばわかりやすいかもしれ ない。もっとも、実行可能形式といえども何らかのプロセッサ（実行エンジン） の力を借りないと機能的実体にはなりえないのだけど。まー、それを言い出す ときりがないので、「実行可能形式=機能的実体」とみなそう。
例えば、x2 - a という式（expression）をソースコードとみなす。が、こ の式には変数（文字記号）xとaが含まれるから、変数xが引数であることを宣 言して、(x)(x2 - a) とでも書こう（(x){return (x2 - a);}ならもっとリアルっぽいかな）。これを「xの関数」としてコンパイル した結果が λ(x)(x2 - a) なのである（普通は、xを括弧で囲む代わりにピ リオドで区切る記法が採用されるが）。
では、λ(x)(x2 - a) に含まれる変数aは何なのか、と言えば、コンパイル された形式が実行されるときに、外部（実行環境）から受け取る値で具体化さ れるパラメータである。「a」という名前は、適当なメモリを指すようにコン パイルされるから、aは実行時のメモリ状況から決まると言ってもいい。
結局、λ(x)(x2 - a) は、実行環境からaの値を受け取って、引数x（これ はレジスタとかスタックに積まれる）に対して出力値を計算する機能実体 を表すことになる。
以上は、“インフォーマルなラムダ記法”のインフォーマルな説明になって いる。“フォーマルなラムダ式”でも、このような解釈が（少なくとも心情的 には）背景にあるといってよい。
先のτ（零点集合からの選択）とλ（ラムダ記法）を組み合わせると、 τ(λx.(x2 - 2)) は意味を持つ。τ(λx.(x2 - 2)) は特定の実数を表す が、多項式 x2 - 2 から特定の実数に至る道筋は「式→関数→方程式→解集 合→一点の選択」となる。「なんと面倒な！」と感じるかも知れないが、あな たは中学校でこの道筋を経験しているはずだ。それは次のようなものだ。
τ(λx.(x2 - 2)) は、「x2 - 2 = 0 の解の非負のほう」である。そう、 これは「ルート2」に他ならない。さて、τ(λx.(x2 - 2)) を τx.(x2 - 2) と略記することにしよう（λとτを一緒にしたオペレータを あらためてτを書く）。こう書くと、τは、式（項）から特定の実数を作り出 すオペレータのように思える。実際、τx.(x2 - 5) は「5の平方根」を表す し、τx.(x3 - 2) なら「2の立方根」を表す。τを使えば、√とか3√ のような新しい記号（これらは1引数関数記号である）を導入する必要はない。 （もちろん、新しい関数記号を使えば表現が煩雑になるのを避けることができ るが。）
この記事では、「算術的」という形容詞を、小学校の算数と中学校の数学で 習うような内容を示すときに使うことにする(*注13)。算術演算とはいわゆる 四則演算のことだし、算術方程式とは「一変数多項式・イコール・ゼロ」とい う形の方程式だとしよう。この「算術的」の使い方はこの記事だけの用語法だ から注意（一般的に、初等代数的と呼ばれるような範囲のものだろ う）。また、「式」という言葉は、形式的体系におけるformulaに限らず、記 号的表現一般を指すためにも使う（つまり、日常的な用法）。
「算術的」は「数論的」と同義の形容詞として使うこともある。この意味で の算術的は、極めて高度で難しいことになってしまう。
さて、算術的な数系（number system）が進化する過程を、形式体系を使って キチンと捉えみよう。具体的には、非負整数 0, 1, 2, 3, ... が知られてい る状況に対して、逆数（割り算と言っても同じ）と平方根を導入する過程を 算術テンプレートを使って定式化する。算術テンプレートが理解できれば、 再帰テンプレートはほとんど同じものである。
最初にベースとなる形式的体系を定義する。
この形式的体系を常識的（あるいは標準的）に解釈すると、記号「-」は引き 算である。引き算があるので負の整数を (0 - 1)のように表現できる（一意的 ではない）。が、この方式よりは、次のどちらかのほうが多いだろう。
こうして見ると、記号「-」は、定数記号の一部、単項の符号反転演算、2項 の引き算と、3用法でオーバーロードされているわけで、その解釈は難しい。
余談だが、普通の教育でも、記号のオーバーロード、演算の多態性、構文の 曖昧性などが理解のネックとなっている可能性を配慮した方がいいと思う。
この形式的体系の変数記号集合F = (F0, F1, F2, ...)を明確に定義すれば：
変数集合Xは適当に選んで（なんでもよい）TermF(X)を作る。項+(2, 3)、 ×(2, 3)などは中置の(2 + 3)、2×3 にして、さらに×は適宜省略する。要す るに、なるべく“普通”の書き方をする。
変数yとzは変数集合Xに含まれないとして、2つの項 yz - 1 と z2 - y を考える。もちろん、正式に書けば -(×(y, z), 1) と -(×(z, z), y) であ る。yz - 1 も z2 - y もTermF({y, z})には入るが、TermF(X)には所属 していないことに注意せよ。
yz - 1 と z2 - y は算術テンプレートの実例であり、それぞれ、逆数と平 方根を導入するために使う。平方根は前節で触れたから、逆数のためのテンプ レート yz - 1 を説明しよう。
この形式的体系には、非負の整数（を表現するつもりの記号）1, 2, 3, ... は含まれるが、その逆数 1-1、1-1, 2-1, 3-1, ...や、より 一般の“分数”を表現する手段はない。ここでは、個々の逆数／分数ではなく て、むしろ逆数を取る関数<x |→ x-1> (*注15)の導入を目的にしたい。 分数は逆数と積（掛け算）から構成できる。
<x |→ … x …>は、内容的なラムダ記法の別表記である。 「よく使う記法など」を参照。
例えば、2の逆数2-1を考えると、これは「方程式 2×z = 1 を満たす唯 一の数z」として特徴付けられる。少し書き換えれば、「2×z - 1 = 0 である ようなz」である。一般に関数fの零点をZ(f)と書いたのだから、この特徴付け は、「Z(λz.(2×z - 1)) の唯一の点」と書ける。Z(f)から1点を選ぶ出す方 法が決まっているとき、その一点をτ(f)と書く約束だった ので、2の逆数2-1に対する表現は、τ(λz.(2×z - 1))となる。「λとτ を一緒にしたオペレータをあらためてτを書く」流儀を採用すると、τz.(2z - 1) と簡略化できる（掛け算の×も省略した）。
以上は、特定の数2に対する逆数の話だっが、3の逆数ならτz.(3z - 1)だし、 項(x + 1)に対する逆数なら、τz.(2(x + 1) - 1)と書ける。一般に、項tの逆 数の表記は τz.(tz - 1) となる。
先に出した式 yz - 1 を使えば、「項tの逆数を表す表現」は次のような手順 で作れる。この手順は完全に機械的／構文的なものである。
ここまで説明すれば、算術テンプレートを定義しても天下りにはならないだ ろう。‘算術テンプレート’とは、TermF({y, z})に属する項である。yz - 1 と z2 - y は実際、TermF({y, z})に属する。この定義だけでは実は意味 がなく、問題は算術テンプレートをどう使うかである。節を改めて続けよ う。
算術テンプレートの使用目的は、前もって与えられた基礎的な形式的体系に、 新しい演算を導入することである。算術テンプレートは、変数yと変数zを含む （可能性がある）が、yを‘テンプレート変数’と呼び、zは‘束縛変数’と呼 ぼう。
変数yとzは、変数集合Xには含まれない記号を選んでいるのでTermF(X)には 含まれない（例えば具体例として、X={x}の状況を想定せよ）。算術テンプレー トを‘具体化’するとは、TermF(X)に属する項（例えば 2 や x + 1）をテン プレート変数yに代入することである。 yz - 1 → 2z - 1、yz - 1 → (x - 1)z - 1 はテンプレート具体化の例である。
算術テンプレートを具体化しても、変数zは残る（可能性がある）。zだけを 含む（実はzを含まなくてもいいが）項に「τz.」を付けた形が‘τ項’であ る。τ項の意味は既に説明した。τz.(2z - 1)は2-1のことだし、τz.((x - 1)z - 1) は (x - 1)-1のことである。算術テンプレート yz - 1 に関 してτ項を導入することは、逆数関数（の記号）を導入することと同じである ことは推測されるだろう。
もともとあった項の集合TermF(X)にτ項を加えて拡張する手順は次のと おりだ。このとき使う算術テンプレートをTとする。
このようにして作ったTerm∞ が、TermF(X)を算術テンプレートTを使っ て拡張（拡大）した項集合である。Term∞は算術テンプレートTに依存し ているので、このTerm∞をArithExtTermF(X; T)と書こう（長ったらし いが）。ArithExtTermF(X; yz - 1)は、逆数が自由に取れるような体系を意 味している(*注16)。
意味論を厳密に定義しているわけではないので、「意味している」と言うの は少し勇み足である。実際は、「意味することを心情的に期待している」と でも言うべき。
前節の定義では、算術テンプレートを1つだけ使って、項集合を拡張したが、 2つ以上の算術テンプレートを同時に使って拡張を行ってもよい。例えば、 ArithExtTermF(X; yz - 1, z2 - y)は、逆数と平方根が自由に取れる体系 だといえる。詳細な定義は省略して実例を出そう。
（srrtは平方根の関数記号だとして）(1 + sqrt(5))/2 は黄金数として知ら れている。黄金数の表現には平方根と割り算（逆数）が必要になる。算術テン プレート z2 - y のテンプレート変数yを5で具体化すれば、z2 - 5 であ り、これをτオペレータで束縛したτz.(z2 - 5)は「z2 - 5 = 0 であるよう なzの非負のほう」だからsqrt(5)に他ならない。一方、算術テンプレート yz - 1 のテンプレート変数yを2で具体化すれば、2z - 1 であり、これをτオペレー タで束縛したτz.(2z - 1)は1/2に相当する。 したがって、(1 + τz.(z2 - 5))×τz.(2z - 1) が黄金数の表現になっている。
さて、今までの定義では、1/0に相当するτz.(0z - 1) や、sqrt(-1)に相当 するτz.(z2 - (0 - 1))なども項として許されている。意味的に考えれば （実数の範囲内で考える）、このような項はまずい。 τz.(0z - 1)やτz.(z2 - (0 - 1))の扱いには2つの方法がある。
いずれの方法でも、論理式（formula）と演繹系（deduction system）がない と、ちゃんとした扱いはできない。それは、本記事の範囲を越えるから、上記 の注意だけにとどめる。ただし幸いに、正規構造の主たるターゲット分野であ る形式言語理論では、このての問題はほとんど起きない。
‘再帰テンプレート’の定義は算術テンプレートとほとんど同じである。違 いは、算術的方程式「項・イコール・ゼロ」の代わりに再帰方程式（不動点方 程式）「変数・イコール・項」を考える点だけである。下の表に両者の対応を 示す。
| 算術テンプレート | 再帰テンプレート | |
|---|---|---|
| 方程式の形 | 項 = 0 | 変数 = 項 |
| 解集合 | 零点集合Z(f) | 不動点集合Fix(f) |
| 解の一意選択方法 | いろいろ | 最小点 |
| オペレータ記号 | τ（この記事のみ） | μ（伝統的） |
| 拡張した項集合 | ArithExtTermF(X; T) | RecExtTermF(X; T) |
常識的な引き算や零の概念があるなら、再帰方程式 x = f(x) は算術的方程 式 x - f(x) = 0 と変わりはない。よってこの場合は、再帰テンプレートは算 術テンプレートに帰着されてしまう。しかし、「常識的な引き算や零の概念」がい つでもあるとは限らない。実際、Kleene代数では、（零はあるが）合理的な引 き算は定義できない。よって、再帰テンプレート（例えば、1 + yz）は固有の 意味を持つ。
基本となる項集合TermF(X)に対して、いくつかの再帰テンプレートが指定 されると、正規構造の構文パートは決定される。つまり、正規構造の構文パー トは、次のもので指定される。
Kleene構造は正規構造の特殊な例である。Kleene構造の構文パートを与える データは次のとおり。
TermF(X)を拡張してRecExtTermF(X; T)を作る方法は、第7節 で述べた方法でも、第12節の方法でも同じである。
関数（記号）集合F、変数（記号）集合X、いくつかの再帰テンプレートT1, ..., Tkが与えられると、基本となる項集合TermF(X)、μ項で拡張した項 集合RecExtTermF(X; T1, ..., Tk)などは自動的に定義できる。これら の構文的な存在物に意味を与えるとは次のことである。
最も重要な点は、μ項の解釈が最小不動点であることだ。再帰 テンプレートTを具体化した結果T[t/y]は、束縛変数zを含む。この変数zを “領域Dを走る独立変数”と解釈すれば、λz.T[t/y] はDからDへのホントの関 数と解釈できる（もちろん、T[t/y]内の関数記号と変数記号も、ホントの関数 と付値で解釈する）。
与えられた構文と意味が「正規」であるためには、次の条件を要求する。
記号的な存在Sの意味を一律にM[S]と表すことにして、 RecExtTermF(X; T1, ..., Tk) の意味定義をまとめてみる。tは（拡張 された）項であり、Tは再帰テンプレートのどれか（どれでも）ひとつを表す とする。
正規構造が与えられた（または与えられる予定の）とき、RecExtTermF(X; T1, ..., Tk)のメンバーを‘正規項’と呼び、RecExtTermF(X; T1, ..., Tk)をRegTermF(X; T1, ..., Tk)とも書く。
XMLを扱うには、いままで定義した正規構造ではやや不足で、変数にソート （型）が必要である。「『正規（regular）』とは何なん だ」の第8節と同様にTiny Toy XMLで考える。ソート（型）は、Name、List、 Treeである。
List型テンプレート変数yとTree型束縛変数zを含む再帰テンプレートを、次 の（インフォーマルな）パターンで定義する。
<a/> | <a>y z</a>
テンプレート変数yを <b/>|<c/> で具体化すると、次のようになる。
<a/> | <a>(<b/>|<c/>) z</a>
束縛変数zに対してμオペレータを作用させてμ項を作ると：
μz.[<a/> | <a>(<b/>|<c/>) z</a>]
このμ項が何を意味するかというと、次の再帰方程式（不動点方程式）の最 小解である。
z = <a/> | <a>(<b/>|<c/>) z</a>
z = 0 = {} から始めて、近似列を作ろう。パターンはブラケットで囲み、 集合はブレイスで囲んで表記する。
z0 = {}
z1 = [<a/> | <a>(<b/>|<c/>){}</a>]
= {<a/>}
z2 = [<a/> | <a>(<b/>|<c/>){<a/>}</a>]
= {<a/>, <a><b/><a/></a>, <a><c/><a/></a>}
z3 = [<a/> | <a>(<b/>|<c/>){<a/>, <a><b/><a/></a>, <a><c/><a/></a>}</a>]
= {<a/>,
<a><b/><a/></a>, <a><b/><a><b/><a/></a></a>, <a><b/><a><c/><a/></a></a>,
<a><c/><a/></a>, <a><c/><a><b/><a/></a></a>, <a><c/><a><c/><a/></a></a>
}
...
μ項 μz.[<a/> | <a>(<b/>|<c/>) z</a>] は、Tiny Toy XMLに対する一種の 正規表現であり、いくらでも（インスタンスの）入れ子を許すので、無限個の インスタンスにマッチするパターンと解釈できる。項 μz.[<a/> | <a>(<b/>|<c/>) z</a>] を、他のパターンに含めることもできる。 例えば、μz.[<b/> | <b>μz.[<a/> | <a>(<b/>|<c/>) z</a>] z</b>] はより 複雑な正規表現である。