形式言語理論（読み）けいしきげんごりろん

改訂新版　世界大百科事典

形式言語理論 (けいしきげんごりろん)
formal language theory

人間の思考過程を記号で表してコンピューターで扱う機械翻訳のような試みに最も直接に関係する学問は，われわれが日常使用している言語，つまり自然言語に関する学問であろう。自然言語を文字，記号で表されるものに限ると，この学問は，語の形を論ずる語形論morphology，文の構成規則を明らかにする構文論syntax，および文の意味を扱う意味論semanticsの3部門に分かれるが，1956年ころ，アメリカの言語学者N.チョムスキーが構文規則に対して数学模型を与えたことがきっかけとなって，数学的文法論を展開する形式言語理論（以下言語理論という）の研究が盛んになった。その直後に，人工の言語であるプログラミング言語ALGOL（アルゴル） 60の文法が形式文法を用いて記述されたことによって，この理論がプログラミングに対しても強いかかわりをもつことの認識が高まり，言語理論に基づいたプログラミング言語処理の種々の技法が開発されて，実用化されるようになった。

　言語を形式的に扱うために，まずはじめに有限個の文字の集合を定め，これをアルファベットと呼ぶことにする。アルファベットをAとしよう。Aに属する文字を有限個並べたものを，Aの上の語（あるいは文）という。自然言語と異なり，形式言語では語のもつ意味はいっさい考慮されない。語の集合を言語という。したがって，言語にほどこされる基本演算は集合算である。言語理論における基本的な関心事は，ある言語はどのような手順で生成されるのか，ある言語は他の言語にどのようにして変換（翻訳）されるのかということである。これらのことは，結局は語を書き換える規則を導くことに帰着されるのであり，そのための理論的体系付けには，数学基礎論における公理系理論の形式化の方法が用いられる。

　公理系による数学理論では，あらかじめ用意されているいくつかの公理に対して，数学的に正しいと判断される推論を幾回か繰り返し適用することによって定理が証明される。このとき，推論の過程に直感が介入することを避けようとすると，推論自体を形式化することが必要となる。そこで，公理，推論規則の両方をあるアルファベット上の語で与えるようにした抽象的システムを形式的体系formal systemと呼んでいる。いまu，v，x，yを語として，ある語がx u yと書かれるとする。一方，推論規則はu→vのように表され，この規則によってuがvに書き換えられて，語x v yが導かれる。これは，OY→OYSという規則を用意して，BOYをBOYSに書き換えるようなことに相当する。公理に推論規則を幾回か適用して導かれた語は，定理といわれる。推論規則がu→vのように表され，かつ公理が1個だけである体系は準-Thueシステムといわれ，代表的な言語理論であるチョムスキーの理論は，直接このシステムから導かれている。

　準-Thueシステムは3項組T＝（A，α，P）で与えられる。ここに，αは公理といわれる一つの語，Pはプロダクションと呼ばれる推論規則の集合，Aは公理とプロダクションに現れるすべての記号の集合，つまりTのアルファベットである。たとえば，システムをT₁＝（A₁，α₁，P₁）とし，ただしA₁＝｛the，a，father，mother，doll，toy，makes，S，N_p，V_p，A，N，V｝，α₁＝Sであり，P₁は次のプロダクションからなるものとする。（1）S→N_pV_p，（2）N_p→AN，（3）V_p→VN_p，（4）A→the，（5）A→a，（6）N→father，（7）N→mother，（8）N→toy，（9）N→doll，（10）V→makes→（11）V→eats。公理Sに（1）（2）（3）（2）をこの順にほどこした結果に（4）（6）（10）（5）（8）を適用すると，the father makes a toyという語が得られ，これ以上プロダクションは適用できない。このような語は終端定理といわれる。このシステムはthe doll eats a motherのような意味的には不適当な英文と思われる語も生成する。

　次に，システムT₂＝（A₂，α₂，P₂）では，A₂＝｛σ，a，＋，－，×｝，α₂＝σであり，P₂は次のプロダクションよりなるものとする。（1）σ→a，（2）σ→＋σσ，（3）σ→－σσ（4）σ→×σσ。たとえば，公理σに対し，はじめに（4）を適用すると×σσが得られ，次いで（2）を2回適用すると×＋σσ＋σσが，最後に（1）を4回適用すると終端定理の一つである語×＋aa＋aaが導かれる。ここで，二項演算子・を用いた記法・aaはa・aと同じ意味をもつとすると，いま導かれた語は（a＋a）×（a＋a）という算術式を表す。このように演算子を被演算項に先行させる記法は逆ポーランド記法といわれ，括弧を省略するのに役立つ。システムT₃は加減算と乗算とからなる算術式の集合としての言語を生成する。

　上記のような語の書換えシステムにおいて，書換え規則を種々定義することにより，いろいろな言語の体系が定義されるが，それらの中で最もよく研究され，かつ応用もされているのはチョムスキーの句構造文法による言語体系である。通常，言語理論というとこの言語体系の理論を指すことが多い。句構造文法では，準-Thueシステムのプロダクションの左辺に現れる記号を非終端記号と呼んで，その全集合をV_nで表す。また，終端定理にかぎってそれを語と呼び，語を構成する記号を終端記号と呼んでその全集合をV_tで表す。T₃＝（V_n，V_t，P，σ）とすると，V_n＝｛S，N_p，V_p，A，N，V｝，V_t＝｛the，a，father，mother，doll，toy，makes，eats｝，σ＝Sとなる。

　公理の記号Sは文の概念に，非終端記号は文の下位概念である句，節の概念に，また終端記号は文をつづる最下位の文字概念に対応する。任意の語がある言語に属するかどうかの決定問題や種々の演算により，言語が属する族がどのような族になるかを決定する問題などが理論的な興味の対象となる。
執筆者：福村 晃夫

出典　株式会社平凡社「改訂新版　世界大百科事典」

世界大百科事典（旧版）内の形式言語理論の言及

【オートマトン】より

…また当時，自然言語学者のチョムスキーN.Chomskyによって，自然言語を形式的に扱おうという試みがなされた。この理論は，計算機のプログラム言語の設計に強い影響を与え，形式言語理論として確立していく。形式言語理論は，言語をいかに定義するかということ，すなわち，与えられた文が文法的に正しいかどうかをどのように規定するかに関する理論であり，一方，オートマトン理論は言語の認識に関する理論ととらえられた。…

【自然言語処理】より

…プログラム言語のような人工的に設計された人工言語に対して，歴史的経緯を経て自然発生的に形成された日本語や英語のような言語を自然言語という。両者の区別は自明ではないが形式言語理論によれば，その文法の数学的性質は明らかになる。さて，自然言語を扱う学問として歴史的には言語学がある。…

【チョムスキー】より

…　また彼は，この理論の初期の頃，その具体的な方針を検討することとの関連において，文法の数学的モデルを幾通りか立て，それらの純粋に数学上の見地からの研究も併せて行った。プログラム言語との関連やオートマトンとの対応を浮かび上がらせたその興味深い成果は，数学者の注目するところとなり，これを端緒に人工言語に関する数学上の研究が発展，〈形式言語理論〉などと呼ばれて数学の一分野をなすにいたっている。つまり彼はこの分野の創始者でもあるわけだが，彼にとっては，こうした研究の主旨は〈いやしくも人間の言語の文法を構築するには，マルコフ過程などの単純なモデルでは不適切で，“変形”が必要だ〉と論証することにあったようで，そののち彼自身はこの方面から離れている。…

※「形式言語理論」について言及している用語解説の一部を掲載しています。

出典｜株式会社平凡社「世界大百科事典（旧版）」