形式言語 形式言語の概要

形式言語

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/08/14 01:18 UTC 版)

ナビゲーションに移動 検索に移動

定義

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

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

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

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

  • 「連結」 は、文字列群 から構成される。ここで、 に含まれる文字列で、 に含まれる文字列である。
  • 「積集合」 は、 にも にも含まれる文字列の集合である。
  • 「和集合」 は、 に含まれる文字列の集合である。
  • の「補集合」は、 に含まれない全ての文字列の集合である。
  • 「商集合」 は、 に含まれる文字列 に対して、 に含まれる文字列 が存在するときに、全ての に相当する文字列群から構成される。
  • クリーネスター は、 という形式の全文字列群から構成される。ただし、 に含まれ、 である。注意すべきは、 の場合もあるので、空文字列 も含まれるという点である。
  • 「反転」 は、 の全文字列を反転させた文字列群から構成される。
  • の「シャッフル」とは、 で表される全文字列から構成される。ここで、 で、 を連結した に含まれる文字列であり、 を連結した に含まれる文字列である。

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

形式文法

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

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

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

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

...

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

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


  1. ^ Micael Sipser (2005). Introduction to the Theory of Computation. ISBN 0534950973. 
  2. ^ 坪井明人 (2011年). “数学基礎論サマースクール モデル理論入門”. 2012年2月18日閲覧。


「形式言語」の続きの解説一覧



形式言語と同じ種類の言葉


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「形式言語」の関連用語

形式言語のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



形式言語のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの形式言語 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2021 Weblio RSS