形式言語

形式言語(けいしきげんご、英: formal language)とは、文法や構文, 統語論などが、すべて形式的に与えられている言語である。人工言語の一種^[1] 。

形式的でないために、しばしば曖昧さが残されたり、話者集団によって用法がうつろいていったりする自然言語に対して、形式言語は、用法の変化に関しては非常に厳格である。

この記事では、形式的な統語論すなわち構文の形式的な定義と形式文法について述べる。形式的な意味論については形式意味論の記事を参照。

形式言語の理論、特にオートマトン理論と関連したそれにおいては、言語はアルファベットの列(語 word) の集合である^[2] 。

${\displaystyle L\subset \Sigma ^{*}=\{\langle \sigma _{1},\sigma _{2},...\rangle |\sigma _{i}\in \Sigma \}}${\displaystyle L\subset \Sigma ^{*}=\{\langle \sigma _{1},\sigma _{2},...\rangle |\sigma _{i}\in \Sigma \}}

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

あるチューリングマシンが存在して、言語に属するすべての語 w に対して動作させると受理状態で停止し、属さない語には受理しないようなとき、その言語はチューリング認識可能という。 また、言語に属さないときは必ず拒否状態で停止する場合、その言語はチューリング判別可能であるという。(この2つの違いは、一部の入力に対してチューリングマシンが停止しない場合があるかどうかである) また、チューリングマシンTMの言語 L(TM) とは、テープに w をセットしたあと、TMを動作させると受理状態に入って停止するような w の集合からなる言語(TM認識可能な言語)のことである。

この言語には以下のような演算が定義される。ここで、${\displaystyle L_{1}}${\displaystyle L_{1}} と ${\displaystyle L_{2}}${\displaystyle L_{2}} は共通のアルファベットから構成される言語であるとする。

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

モデル理論においては、言語は定数記号、関数記号、述語記号の集合である^[3] 。

${\displaystyle L=\{c_{0},c_{1},...\}\cup \{f_{0},f_{1},...\}\cup \{p_{0},p_{1},...\}}${\displaystyle L=\{c_{0},c_{1},...\}\cup \{f_{0},f_{1},...\}\cup \{p_{0},p_{1},...\}}

形式言語は、形式文法と密接な関係がある。例として、次のような文脈自由文法の構文規則があるとき、

• 名詞句 ::= 名詞 | 形容詞 名詞 | 名詞句 "を" 動詞 "ている" 名詞句
• 動詞 ::= "見"
• 名詞 ::= "猿" | "飼育員"
• 形容詞 ::= "小さい"

以下のように規則を再帰的に適用して、その言語の要素(名詞句)を列挙することができる。

1. (猿 飼育員 小さい猿 小さい飼育員)
2. (猿 飼育員 小さい猿 小さい飼育員 猿を見ている猿 猿を見ている飼育員 猿を見ている小さい猿 ... 小さい猿を見ている猿 ...)
3. (猿 飼育員 小さい猿 小さい飼育員 猿を見ている猿 ... 猿をみている猿を見ている猿 ... 小さい猿を見ている猿を見ている小さい飼育員を見ている猿 ...)

...

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

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

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

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

自然言語を比較的単純な形式言語のモデルにあてはめて分析する言語学は、チョムスキーによって提唱された。音素や語幹などを素記号として考える。 実際の自然言語の構文規則(あるいは文法)は、文字通り自然発生的のものであり、形式言語における構文規則のように明確に規定するのは難しい。

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

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

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

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

• 文法
• 理論計算機科学
• 形式言語
• 構文解析 (プログラミング)
• 数学に関する記事
• メタ論理学

• 独自研究の除去が必要な節のある記事/2015年7月-12月
• BNF識別子が指定されている記事
• BNFdata識別子が指定されている記事
• GND識別子が指定されている記事
• J9U識別子が指定されている記事
• LCCN識別子が指定されている記事
• NDL識別子が指定されている記事
• NKC識別子が指定されている記事