形式言語
数理論理学や計算機科学、言語学において、形式言語（けいしきげんご、テンプレート:Lang-en-short）あるいは単に言語とは、記号列もしくは記号の集合のこと。
定義
形式言語の理論、特にオートマトン理論と関連したそれにおいては、言語はアルファベットの列（語 word) の集合である。[1]
<math>L \subset \Sigma^* = \{ \langle \sigma_1, \sigma_2, ... \rangle |\sigma_i \in \Sigma\}</math>
ただし、長さゼロの空単語（Empty Word, 記号 <math>e</math>、<math>\epsilon</math>、<math>\Lambda</math>)も含む。 チューリングマシンの言語は単なる文字列なので、数学的構造(他のチューリングマシンを含む)を扱うには符号化(エンコード)し、その数値を解釈するプログラムを埋め込む必要がある。 チューリング完全機械は十分強力なので、この手法であらゆる列挙可能な構造を扱うことができる。チューリングマシンの数値表現については(チューリングマシンの)表記(description)という。
あるチューリングマシンが存在して、言語に属するすべての語 w に対して動作させると受理状態で停止し、属さない語には受理しないようないとき、その言語はチューリング認識可能という。 また、言語に属さないときは必ず拒否状態で停止する場合、その言語はチューリング判別可能であるという。(この２つの違いは、一部の入力にたいしてチューリングマシンが停止しない場合があるかどうかである) また、チューリングマシンTMの言語 L(TM) とは、テープに w をセットしたあと、TMを動作させると受理状態に入って停止するような w の集合からなる言語(TM認識可能な言語)のことである。
この言語には以下のような演算が定義される。ここで、<math>L_{1}</math> と <math>L_{2}</math> は共通のアルファベットから構成される言語であるとする。
- 「連結」<math>L_{1} L_{2}\quad</math> は、文字列群 <math>vw</math> から構成される。ここで、<math>v</math> は <math>L_{1}</math> に含まれる文字列で、<math>w</math> は <math>L_{2}</math> に含まれる文字列である。
- 「積集合」<math>L_1 \cap L_2</math> は、<math>L_{1}</math> にも <math>L_{2}</math> にも含まれる文字列の集合である。
- 「和集合」<math>L_1 \cup L_2</math> は、<math>L_{1}</math> か <math>L_{2}</math> に含まれる文字列の集合である。
- <math>L_{1}</math> の「補集合」は、<math>L_{1}</math> に含まれない全ての文字列の集合である。
- 「商集合」<math>L_{1}/L_{2}\quad</math> は、<math>L_{1}</math> に含まれる文字列 <math>vw</math> に対して、<math>L_{2}</math> に含まれる文字列 <math>w</math> が存在するときに、全ての <math>v</math> に相当する文字列群から構成される。
- 「クリーネスター」<math>L_{1}^{*}</math> は、<math>w_{1}w_{2}...w_{n}</math> という形式の全文字列群から構成される。ただし、<math>w_{i}</math> は <math>L_{1}</math> に含まれ、<math>n \ge 0</math> である。注意すべきは、<math>n = 0</math> の場合もあるので、空文字列 <math>\epsilon</math> も含まれるという点である。
- 「反転」<math>L_{1}^{R}</math> は、<math>L_{1}</math> の全文字列を反転させた文字列群から構成される。
- <math>L_{1}</math> と <math>L_{2}</math> の「シャッフル」とは、<math>v_{1}w_{1}v_{2}w_{2}...v_{n}w_{n}</math> で表される全文字列から構成される。ここで、<math>n \ge 1</math> で、<math>v_{1},...,v_{n}</math> を連結した <math>v_{1}...v_{n}</math> は <math>L_{1}</math> に含まれる文字列であり、<math>w_{1},...,w_{n}</math> を連結した <math>w_{1}...w_{n}</math> は <math>L_{2}</math> に含まれる文字列である。
モデル理論においては、言語は定数記号、関数記号、述語記号の集合である。[2]
<math>L = \{ c_0, c_1, ...\} \cup \{ f_0, f_1, ...\} \cup \{ p_0, p_1, ... \}</math>
これらの記号に意味を与える構造は、言語の対象外である。
形式文法
形式言語は、形式文法と密接な関係がある。文法を再帰的に適用すると、形式言語を定義することができる。これを形式文法Rの言語L(R)という。 たとえば、以下のような文脈自由文法
- 名詞句 ::= 名詞 | 形容詞 名詞 | 名詞句 "を" 動詞 "ている" 名詞句
- 動詞 ::= "見"
- 名詞 ::= "猿" | "飼育員"
- 形容詞 ::= "小さい"
にたいして、再帰的に文法を適用すると、以下のように言語(名詞句)の要素を列挙することができる。
- (猿 飼育員 小さい猿 小さい飼育員)
- (猿 飼育員 小さい猿 小さい飼育員 猿を見ている猿 猿を見ている飼育員 猿を見ている小さい猿 ... 小さい猿を見ている猿 ...)
- (猿 飼育員 小さい猿 小さい飼育員 猿をみている猿 ... 猿をみている猿をみている猿 ... 小さい猿を見ている猿を見ている小さい飼育員を見ている猿 ...)
... とこのような操作を無限回繰り返せば、この文法によって生成される言語が得られる。
また、形式文法が階層をなすというチョムスキー階層は、生成する言語では言語の認識に必要な最小のオートマトンが階層をなすという形で現れる。
言及される分野
形式言語は、「人や計算機の如何なる記号変換能力から如何なる思考能力や計算能力が生まれるか」の学としての広義の数理論理学の研究対象であり、従って形式言語は、哲学・言語学・計算機科学・数学基礎論・数理心理学等々において重要な役割を演ずる。 それらの学問分野では、如何なる形式言語を研究すべきかの文法論（構文論・統辞論）や形式言語の意味論や演繹論が研究される。
自然言語への応用
自然言語を比較的単純な形式言語のモデルにあてはめて分析する言語学は、チョムスキーによって提唱された。音素や語幹などを素記号として考える。 実際の自然言語の構文規則（あるいは文法）は、文字通り自然発生的のものであり、形式言語における構文規則のように明確に規定するのは難しい。
ただ、素朴な文法論の主張は、形式言語の理論とみなすことができる。 素朴な文法論は、例えば次ようなものである。
こういう文法論はすなわち、素記号とは何かを定め、それらから文を作る構文規則を定めるのだから、まさに形式言語の理論である。
こういう形式言語論的な文法論は、実際の言語と比較することで自然言語の特徴を浮き彫りにし、自然言語のより深い理解へと導くことを可能とすることもなくはない。言語そのものではなく、言語行動の深層をなす人間精神を探るためには、むしろこういう文法論を数学化し、更に意味論・文法論を伴った論理学にまで推し進めることが有意義ともいえよう。
