形式言語のソースを表示

'''形式言語'''（けいしきげんご、{{lang-en-short|formal language}}）は、その[[文法]]（構文、[[統語論]]）が、場合によっては意味（[[意味論 (曖昧さ回避)|意味論]]）も、形式的に与えられている（[[形式体系]]を参照）[[言語]]である。形式的でないために、しばしば曖昧さが残されたり、話者集団によって用法のうつろいゆくような[[自然言語]]に対して、[[プログラミング言語]]を含む一部の[[人工言語]]や、いわゆる機械可読な（[[機械可読目録]]を参照）ドキュメント類などの形式言語は、用法の変化に関しては厳格である。この記事では形式的な統語論すなわち構文の形式的な定義と[[形式文法]]について述べる。形式的な意味論については[[形式意味論]]の記事を参照。

==定義==
形式言語の理論、特に[[オートマトン|オートマトン理論]]と関連したそれにおいては、言語は[[アルファベット (計算機科学)|アルファベット]]の列（語 word） の集合である<ref>{{cite book|isbn=0534950973|title=Introduction to the Theory of Computation|author=Micael Sipser|year=2005}}</ref>。

<math>L \subseteq \Sigma^* = \{ \langle \sigma_1, \sigma_2, \dots \rangle \mid \sigma_i \in \Sigma \}</math>

ただし、長さゼロの'''空単語'''（''Empty Word'', 記号 <math>e</math>、<math>\epsilon</math>、<math>\Lambda</math>）も含む。
チューリングマシンの言語は単なる文字列なので、数学的構造(他のチューリングマシンを含む)を扱うには符号化([[エンコード]])し、その数値を解釈するプログラムを埋め込む必要がある。
チューリング完全機械は十分強力なので、この手法であらゆる列挙可能な構造を扱うことができる。チューリングマシンの数値表現については(チューリングマシンの)表記(description)という。

あるチューリングマシンが存在して、言語に属するすべての語 ''w'' に対して動作させると受理状態で停止し、属さない語には受理しないようなとき、その言語は'''チューリング認識可能'''という。
また、言語に属さないときは必ず拒否状態で停止する場合、その言語は'''チューリング判別可能'''であるという。(この2つの違いは、一部の入力に対してチューリングマシンが停止しない場合があるかどうかである)
また、チューリングマシン'''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> に含まれる文字列である。

[[モデル理論]]においては、言語は定数記号<!-- TMにおける2進表現文字列に相当 -->、関数記号<!-- 変換TMの文字列表現に相当 -->、述語記号<!-- 判別TMの文字列表現に相当 -->の集合である<ref>{{Cite web|和書|url=http://www2.kobe-u.ac.jp/~kikyo/LogicSummerSchool2011/lectures/2011kobe_tsuboi.pdf|accessdate=2012-02-18|title=数学基礎論サマースクール モデル理論入門|year=2011|author=坪井明人}}</ref>。

<math>L = \{ c_0, c_1, ...\} \cup \{ f_0, f_1, ...\} \cup \{ p_0, p_1, ... \}</math><!--

これらの記号に意味を与える構造は、言語の対象外である。{{要出典範囲|つまり何らかの実際的な問題を言語の認識問題として定式化するには、その問題に共通する制約を構造として定義しておく必要がある。そしてそれらの定数や関数、述語を充足する問題を言語の認識問題とすることができる。}} ちょっと自信が無い --><!--「言語の対象外」というのも多分英語版執筆者(？)の独断？　形式言語にだって意味論はあるというか-->

==形式文法==
{{Main|形式文法}}
形式言語は、[[形式文法]]と密接な関係がある。例として、次のような[[文脈自由文法]]の構文規則があるとき、
* 名詞句 ::= 名詞 | 形容詞 名詞 | 名詞句 "を" 動詞 "ている" 名詞句
* 動詞 ::= "見"
* 名詞 ::= "猿" | "飼育員"
* 形容詞 ::= "小さい"
以下のように規則を再帰的に適用して、その言語の要素(名詞句)を列挙することができる。
# (猿 飼育員 小さい猿 小さい飼育員)
# (猿 飼育員 小さい猿 小さい飼育員 猿を見ている猿 猿を見ている飼育員 猿を見ている小さい猿 ... 小さい猿を見ている猿 ...)
# (猿 飼育員 小さい猿 小さい飼育員 猿を見ている猿 ... 猿をみている猿を見ている猿 ... 小さい猿を見ている猿を見ている小さい飼育員を見ている猿 ...)
...

すなわち、このような操作の任意回の繰り返しによって、その言語(文の集合)が得られる。

また、形式文法が階層をなすという[[チョムスキー階層]]は、生成する言語では言語の認識に必要な最小のオートマトンが階層をなすという形で現れる。

==その他==
{{独自研究|date=2015年11月|section=1}}
===言及される分野===
形式言語は、「人や[[計算機]]の如何なる記号変換能力から如何なる[[思考]]能力や[[計算]]能力が生まれるか」の学としての広義の[[数理論理学]]の研究対象であり、従って形式言語は、[[哲学]]・[[言語学]]・[[計算機科学]]・[[数学基礎論]]・[[数理心理学]]等々において重要な役割を演ずる。
それらの学問分野では、如何なる形式言語を研究すべきかの[[文法|文法論]]（構文論・統辞論）や形式言語の[[意味論 (曖昧さ回避)|意味論]]や[[演繹|演繹論]]が研究される。

[[形式手法]]という場合には、形式言語に加えて、検証・証明などの仕組みを込みで言う場合が有る。

===自然言語への応用===
{{see|生成文法|句構造文法}}
[[自然言語]]を比較的単純な形式言語のモデルにあてはめて分析する言語学は、[[ノーム・チョムスキー|チョムスキー]]によって提唱された。[[音素]]や[[語幹]]などを素記号として考える。
実際の自然言語の[[構文規則]]（あるいは[[文法]]）は、文字通り自然発生的のものであり、形式言語における構文規則のように明確に規定するのは難しい。

ただ、素朴な文法論の主張は、形式言語の理論とみなすことができる。
素朴な文法論は、例えば次のようなものである。
* [[品詞]]にはこのようなのものがある。
* この語はあの品詞に属す。
* この品詞に属す語をこの[[活用]]と[[組み合わせ]]と[[順序]]とで並べると文（や[[句]]や[[節 (文法)|節]]）になる。
こういう文法論はすなわち、素記号とは何かを定め、それらから文を作る構文規則を定めるのだから、まさに形式言語の理論である。

こういう形式言語論的な文法論は、実際の言語と比較することで自然言語の特徴を浮き彫りにし、自然言語のより深い理解へと導くことを可能とすることもなくはない。言語そのものではなく、言語行動の深層をなす人間精神を探るためには、むしろこういう文法論を数学化し、更に[[意味論 (曖昧さ回避)|意味論]]・文法論を伴った論理学にまで推し進めることが有意義ともいえよう。

==脚注==
{{脚注ヘルプ}}
{{Reflist}}

{{commonscat|Formal languages}}

{{Logic}}
{{Normdaten}}
{{DEFAULTSORT:けいしきけんこ}}
[[Category:文法]]
[[Category:理論計算機科学]]
[[Category:形式言語|*]]
[[Category:構文解析 (プログラミング)]]
[[Category:数学に関する記事]]
[[Category:メタ論理学]]