形式言語

出典: フリー百科事典『ウィキペディア（Wikipedia）』

形式言語（けいしきげんご）とは、もっとも広義かつ素朴には、素となる記号（これを素記号と仮に呼ぶ）幾つかから、定められた規則（この規則を文法とか構文規則とか統辞規則とかいう）に従って作られる記号の全体の集合のことをいう。ただし、ここで言う記号も、もっとも広義に「何らかの集合の元」を意味する。

[編集] 具体例いくつか

一番簡単な形式言語は、素記号が唯一つあって（それを1で表す）、「記号 a の右側に 1 を書き添えることができる」という構文規則だけのあるものである。この形式言語は、任意長さの 1 の列 11...1 の全体であって、これは自然数の全体にいわゆる後者関数を与えて代数系としたものと同一視される（ペアノの公理参照）。

またたとえば、命題論理学における形式言語（これを命題言語という）においては、素記号（これを変数という）が任意個あって、構文規則には次の二種だけがある。

記号 a, b から記号 a∧b,　a∨b, a⇒b を作ることができる。
記号 a から記号￢a を作ることができる。

変数にこれらの規則を任意回適用して出来る記号の全体が命題言語であり、命題言語の元を論理式と呼ぶ。従ってたとえば、x, y が変数なら (x∧(x⇒y))⇒y は論理式の一つである。

各種プログラミング言語も、素記号と構文規則によって定められた形式言語である。

[編集] 数学的定義

数学の立場から形式言語を定義すれば、普遍類別代数系（普遍性を持つ類別代数系、universal sorted algebra, sorted algebra with universality）となる。そのうち、類が唯一つのものに限定して説明すれば、次のようになる。すなわち、（類が唯一つの）形式言語とは、集合 A とその上の全域的算法族 R および A の部分集合 S との組み(A,R,S)で、次の性質をもつもののことをいう。

A の任意の元は S の有限個の元に R に属す算法を有限回施して得られる。
S から A と同類の任意の代数系 B への任意の写像 f は、A から B への準同形写像 F に拡張される。

この2.の性質が普遍性(universality)と呼ばれ、S と R とが前述の素記号の全体と構文規則の全体とに相当する。

集合 S と算法族 R を任意に与えたとき、(A,R,S)が形式言語となるような集合 A のあることが証明されている。たとえば、 R が ∧,∨,⇒ なる三種の2項算法と1項算法￢とからなる場合、(A,R,S)は S を変数の集合とする命題言語に等しい。

ただし、上記のように「類が唯一つ」と限定すると、たとえば述語言語のような簡単な形式言語の理論さえ含むことができないので（述語言語では類が二個ある）、類が任意個ある場合を考えなければならないが、その場合の説明は割愛する（普遍類別代数系参照）。

なお、たとえば数という概念が必要に応じて自由に広げられてきたように、形式言語という概念も必要に応じて広げ得るものであり、上記の数学的定義に縛られる必要はない。実際、分野により必要に応じ、より広い意味に解されている。

[編集] 如何なる分野に関わるか

形式言語は、「人や計算機の如何なる記号変換能力から如何なる思考能力や計算能力が生まれるか」の学としての広義の数理論理学の研究対象であり、従って形式言語は、哲学・言語学・計算機科学・数学基礎論・数理心理学等々において重要な役割を演ずる。それらの学問分野では、如何なる形式言語を研究すべきかの文法論（構文論・統辞論）や形式言語の意味論や演繹論が研究される。

[編集] 自然言語との関係

自然言語は形式言語と根本的に異なる。自然言語にも素記号に当たるものがある。たとえば、音声言語においては音素が素記号に当たり、文字言語においては漢字や仮名あるいは単語などが素記号に当たり、手話言語においては単位動作が素記号に当たる。しかし自然言語の構文規則（あるいは文法）は、文字通り自然発生的のものであり、形式言語における構文規則のように明確ではない。実際、日本語の文法が如何なるものかという問題については、国語学者の間でも意見の一致がなく、「学者一人につき文法論が一つある」という状態である。自然言語が数学的に定義される普遍類別代数系でないのは勿論である。

ただ、素朴な文法論は、形式言語の理論とみなすことができる。素朴な文法論は、例えば次の類のことを主張する。

品詞にはこれこれのものがある。
これこれの語はこれこれの品詞に属す。
これこれの品詞に属す語をこれこれの活用と組み合わせと順序とで並べると文（や句や節）になる。

こういう文法論はすなわち、素記号とは何かを定め、それらから文を作る構文規則を定めるのだから、まさに形式言語の理論である。

しかし、だからといってこういう形式言語論的な文法論が無意味なのではない。言語そのものではなく、言語行動の深層をなす人間精神を探るためには、むしろこういう文法論を数学化し、更に意味論・文法論を伴った論理学にまで推し進めることが有意義ともいえよう。数学の定理の証明の深層にある思考の原理を探ることから形式言語の数学的理論たる数理論理学に辿りついたのと同様の事情がある。

[編集] 情報工学的定義

計算機科学や論理学の立場から形式言語を定義すれば、有限個の文字から導かれた有限長の単語群（文字列群）の集合となる。

たとえば、文字セットが $\left \{ a , b \right \}$ ならば、そこから $a b a b b a$ というような文字列が生成される。

この文字セットから導出される典型的な言語として $a$ と $b$ を同数含む全ての単語からなる集合が考えられる。

長さゼロの空単語（Empty Word)も許されるものとして、それを $e$ 、 $ε$ 、 $Λ$ などと表す。文字セットが有限集合で文字列は全て有限長だが、言語としては無限個数の文字列を持つ可能性がある（単語長に制限がないため）。

形式言語の例として以下のものがある。

$a, b$ から導きだされる全ての単語の集合
集合 $\left \{ a^{n}\right\}$ において n は素数であり、 $a n$ は $a$ を $n$ 個並べたものとする。
あるプログラミング言語に関して文法的に正しいプログラムの集合。
あるチューリングマシンが停止する入力の集合。

形式言語の表現方法も様々である。

形式文法から生成される文字列群（チョムスキー階層参照）
正規表現から生成される文字列群
チューリングマシンや有限オートマトンのようなオートマトンの受容（認識）する文字列群
YES/NOで答えられる質問の集合に対して、全部にYESと答えられる場合（決定問題参照）

いくつかの操作を施すことによって既存の言語から新たな言語を生成することができる。 $L 1$ と $L 2$ がある共通の文字群から構成される言語であるとする。

「連結」 $L 1 L 2$ は、文字列群 $v w$ から構成される。ここで、 $v$ は $L 1$ に含まれる文字列で、 $w$ は $L 2$ に含まれる文字列である。
「積集合」 $L_1 \cap L_2$ は、 $L 1$ にも $L 2$ にも含まれる文字列の集合である。
「和集合」 $L_1 \cup L_2$ は、 $L 1$ か $L 2$ に含まれる文字列の集合である。
$L 1$ の「補集合」は、 $L 1$ に含まれない全ての文字列の集合である。
「商集合」 $L 1 / L 2$ は、 $L 1$ に含まれる文字列 $v w$ に対して、 $L 2$ に含まれる文字列 $w$ が存在するときに、全ての $v$ に相当する文字列群から構成される。
「クリーネスター」 $L_{1}^{*}$ は、 $w 1 w 2 ... w n$ という形式の全文字列群から構成される。ただし、 $w i$ は $L 1$ に含まれ、 $n \ge 0$ である。注意すべきは、 $n = 0$ の場合もあるので、空文字列 $ε$ も含まれるという点である。
「反転」 $L_{1}^{R}$ は、 $L 1$ の全文字列を反転させた文字列群から構成される。
$L 1$ と $L 2$ の「シャッフル」とは、 $v 1 w 1 v 2 w 2 ... v n w n$ で表される全文字列から構成される。ここで、 $n \ge 1$ で、 $v 1,..., v n$ を連結した $v 1 ... v n$ は $L 1$ に含まれる文字列であり、 $w 1,..., w n$ を連結した $w 1 ... w n$ は $L 2$ に含まれる文字列である。