数理言語(読み)すうりげんご

日本大百科全書(ニッポニカ)の解説

数理言語
すうりげんご

アメリカの言語学者チョムスキーが1956年ごろ与えた文法の数学的模型。言語の構造を記述するのは文法である。the man eats the tomatoという文は、the manという名詞句のあとにeats the tomatoという動詞句が続く。これを
  〈文〉→〈名詞句〉〈動詞句〉
と書く。theは前置詞、man, tomatoは名詞、eatsは動詞、the tomatoは名詞句である。これらには次の文法的関係がある。
  〈名詞句〉→〈冠詞〉〈名詞〉,
  〈動詞句〉→〈動詞〉〈名詞句〉,
  〈名詞〉→man,〈名詞〉→tomato,
  〈冠詞〉→the,〈動詞〉→eats
 次のように、→印の左辺を右辺で書き換える文法的解析を経て、目的の文が得られる。
  〈文〉⇒〈名詞句〉〈動詞句〉
   ⇒〈冠詞〉〈名詞〉〈動詞句〉
   ⇒the〈名詞〉〈動詞句〉
   ⇒the man〈動詞句〉,………
   ⇒the man eats the tomato
 これに倣って、形式的な文法の概念を与える。文から出発して個々の単語に達するのに、文、名詞句、動詞句といった中間の概念を経た。これらを非終端記号とか変数とよぶ。単語に対応するものを終端記号とよぶ。終端記号、非終端記号の有限集合をそれぞれVΣとする。〈文〉を開始記号といい、Sで表すことにする。
  〈名詞句〉→〈冠詞〉〈名詞〉
のような文法規則を生成規則とか書き換え規則という。この規則は一般にα→βの形に表されるが、αとβはVあるいはΣの元の有限列である。生成規則の有限集合をPとすると、G=(Σ, V, P, S)という四重対が得られるが、このGを句構造文法という。文字列w1αw2に規則α→βを適用するということは、αをβと書き換えて、w1βw2と変えることであり、w1αw2w1βw2などと書く。Sから出発して、生成規則を有限回適用して、文字列wが得られたとき、Sからwが導出されたという。文法Gが与えられたとき、SからGの生成規則を用いて導出される終端記号の列wの全体を、Gによって生成される言語という。いま述べてきた文法を句構造文法とか0型文法という。生成規則を、α1Cα2→α1βα2(α1、α2、βはVΣの元の文字列で、α1とα2は空列でもよい。CΣの元)の形に制限したものを文脈依存文法あるいは1型文法という。前後の文脈がα1、α2であるときのみ、変数Cを文字列βに書き換えることを許す。とくに、すべての生成規則のα1とα2が空列であるとき、文脈自由文法あるいは2型文法という。この文法では、生成規則A→βのβはVΣの元の文字列でよいが、AΣの元でなければならない。制限をさらに強めて、ABが変数、aが終端記号のときのみ、AaBあるいはAaの形の生成規則を認める文法を、正規文法あるいは3型文法という。3型文法で生成される言語を正規集合ともいう。0型、1型、2型、3型の各文法で生成される言語は、それぞれチューリング機械、線形有界オートマトン、プッシュダウン・オートマトン、有限オートマトンで受理される文字列の集合と一致する。計算機の発達、普及とともに、数理言語の理論は、プログラム言語の記述、あるいは構文解析とも関連があり、現在では情報科学の重要な一分野になっている。[西村敏男]

出典 小学館 日本大百科全書(ニッポニカ)日本大百科全書(ニッポニカ)について 情報 | 凡例

関連語をあわせて調べる