Up 「自然数のコンピュータ/形式言語」の場合 作成: 2011-10-06
更新: 2011-10-07

    形式言語とは，実際どういうものか？
    例として，＜自然数の計算処理をするコンピュータ＞の形式言語をここで考えてみる。

    この形式言語は，数学の自然数の定義を手本にしてつくることになる。 なぜなら，数学の自然数の定義は，＜生成的＞の完成した形にすでにつくられているからである。

    数学の自然数の定義は，つぎのようになっている：
    1. 自然数の系の定義
        自然数の系は，先ず，集合 と， の一つの要素１と，関数ｆ: ─→ の組
        （ ,1,ｆ）　　　　　
        であり，そしてこれについて，以下のことが成立している：

          1°　ｆ(ｘ)＝１となる の要素ｘは存在しない；
          2°　 の要素ｘ,ｙについてｆ(ｘ)＝ｆ(ｙ)ならばｘ＝ｙ；
          3°　 の部分集合 ′ は，つぎの条件を満たすとき，実は と一致している：
            １が ′ の要素になっている；
            ｘが ′ の要素のとき，ｆ(ｘ)も ′ の要素．

    2. 算法の定義
      1. 加法 (和) の定義
          1° ｘ＋1＝ｆ(ｘ)
          2° ｘ＋f(ｙ) ＝ f(ｘ＋ｙ))
          　 (言い換えると，ｘ＋(ｙ＋1)＝(ｘ＋ｙ)＋1 )
      2. 乗法 (積) の定義
          1° ｘ×1＝ｘ
          2° ｘ× f(ｙ) ＝ ｘ×ｙ＋ｘ
          　 (言い換えると，ｘ×(ｙ＋1)＝ｘ×ｙ＋ｘ )

    コンピュータの上の「1, 2, 3, ‥‥」の再現は，自然数の定義のつぎの部分に倣い，生成文法の方法で行う：
      1. １（「系列の最初の項」と読まれることを想定)
      2. 関数ｆ (「f(x)」が「ｘの後者」と読まれることを想定)
      3. 条件 1゜と 2゜
    「1, 2, 3, ‥‥」の和・積の式も，自然数の算法の定義にそのまま倣って，生成文法で定めることができる。

    ここで，「変項」を，生成文法で定める。
    さらに，変項記号を含む和・積の式を，生成文法で定める。

    以上の「式」は，対象式である。
    つぎに，関係式として，等式を生成文法で定める。

    ここで，真理値を導入する。
    すなわち，数ｎに対する等式「ｎ＝ｎ」を真と定める。
    これも，生成の記述法を用いる。

    そして，命題論理のモジュールを加える。
    これで，＜自然数の計算処理をするコンピュータ＞の＜言語処理マシン＞層のできあがりである。

    このコンピュータに対しては，四則計算はもちろん，数の大小の判定，倍数の判定，命題の真偽の判定等々，自然数の処理全般をさせることができる。 すなわち，させたいことのプログラムをつくることができる。