形式言語

形式言語（けいしきげんご、）は、その文法（構文、統語論）が、場合によっては意味（意味論）も、形式的に与えられている（形式体系を参照）言語である。形式的でないために、しばしば曖昧さが残されたり、話者集団によって用法のうつろいゆくような自然言語に対して、プログラミング言語を含む一部の人工言語や、いわゆる機械可読な（機械可読目録を参照）ドキュメント類などの形式言語は、用法の変化に関しては厳格である。この記事では形式的な統語論すなわち構文の形式的な定義と形式文法について述べる。形式的な意味論については形式意味論の記事を参照。
定義.
形式言語の理論、特にオートマトン理論と関連したそれにおいては、言語はアルファベットの列（語 word） の集合である。
formula_1
ただし、長さゼロの空単語（"Empty Word", 記号 formula_2、formula_3、formula_4）も含む。
チューリングマシンの言語は単なる文字列なので、数学的構造(他のチューリングマシンを含む)を扱うには符号化(エンコード)し、その数値を解釈するプログラムを埋め込む必要がある。
チューリング完全機械は十分強力なので、この手法であらゆる列挙可能な構造を扱うことができる。チューリングマシンの数値表現については(チューリングマシンの)表記(description)という。
あるチューリングマシンが存在して、言語に属するすべての語 "w" に対して動作させると受理状態で停止し、属さない語には受理しないようなとき、その言語はチューリング認識可能という。
また、言語に属さないときは必ず拒否状態で停止する場合、その言語はチューリング判別可能であるという。(この2つの違いは、一部の入力に対してチューリングマシンが停止しない場合があるかどうかである)
また、チューリングマシンTMの言語 "L"(TM) とは、テープに "w" をセットしたあと、TMを動作させると受理状態に入って停止するような "w" の集合からなる言語(TM認識可能な言語)のことである。
この言語には以下のような演算が定義される。ここで、formula_5 と formula_6 は共通のアルファベットから構成される言語であるとする。
モデル理論においては、言語は定数記号、関数記号、述語記号の集合である。
formula_46
形式文法.
形式言語は、形式文法と密接な関係がある。例として、次のような文脈自由文法の構文規則があるとき、
以下のように規則を再帰的に適用して、その言語の要素(名詞句)を列挙することができる。
すなわち、このような操作の任意回の繰り返しによって、その言語(文の集合)が得られる。
また、形式文法が階層をなすというチョムスキー階層は、生成する言語では言語の認識に必要な最小のオートマトンが階層をなすという形で現れる。
その他.
言及される分野.
形式言語は、「人や計算機の如何なる記号変換能力から如何なる思考能力や計算能力が生まれるか」の学としての広義の数理論理学の研究対象であり、従って形式言語は、哲学・言語学・計算機科学・数学基礎論・数理心理学等々において重要な役割を演ずる。
それらの学問分野では、如何なる形式言語を研究すべきかの文法論（構文論・統辞論）や形式言語の意味論や演繹論が研究される。
形式手法という場合には、形式言語に加えて、模擬試験、検証・証明などの仕組みを込みで言う場合が有る。
自然言語への応用.
自然言語を比較的単純な形式言語のモデルにあてはめて分析する言語学は、チョムスキーによって提唱された。音素や語幹などを素記号として考える。
実際の自然言語の構文規則（あるいは文法）は、文字通り自然発生的のものであり、形式言語における構文規則のように明確に規定するのは難しい。
ただ、素朴な文法論の主張は、形式言語の理論とみなすことができる。
素朴な文法論は、例えば次のようなものである。
こういう文法論はすなわち、素記号とは何かを定め、それらから文を作る構文規則を定めるのだから、まさに形式言語の理論である。
こういう形式言語論的な文法論は、実際の言語と比較することで自然言語の特徴を浮き彫りにし、自然言語のより深い理解へと導くことを可能とすることもなくはない。言語そのものではなく、言語行動の深層をなす人間精神を探るためには、むしろこういう文法論を数学化し、更に意味論・文法論を伴った論理学にまで推し進めることが有意義ともいえよう。