帰納的可算言語とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 帰納的可算言語の意味・解説 

帰納的可算言語

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2015/04/29 04:58 UTC 版)

帰納的可算言語(きのうてきかさんげんご、: Recursively enumerable language)は、数学論理学計算機科学における形式言語の一種である。部分決定性言語(Partially Decidable Language)、チューリング受理性言語(Turing-recognizable Language)とも呼ぶ。形式言語のチョムスキー階層におけるタイプ-0言語に相当する。全ての帰納的可算言語は複雑性クラス RE に属する。

定義

帰納的可算言語には以下の3つの等価な定義がある。

  1. 帰納的可算言語は、形式言語アルファベットから生成可能な全ての単語の集合のうち、帰納的可算部分集合である。
  2. 帰納的可算言語は、その言語に含まれる全文字列を数え上げるチューリング機械(または計算可能関数)が存在する形式言語である。言語が無限である場合、同じ文字列が現れないようなアルゴリズムが必要である。すなわち、n 番目の文字列が以前に出現しているかどうかを判定し、もし既出であったら n+1 番目の文字列を代わりに出力する。ただし、その n+1 番目の文字列も既出でないか確認が必要である。
  3. 帰納的可算言語は、入力された文字列がその言語に含まれる場合にそれを受理して停止するチューリング機械(または計算可能関数)が存在する形式言語である。ただし、入力された文字列がその言語に含まれない場合、停止して拒絶するかもしれないし、無限ループするかもしれない。帰納言語は常にチューリング機械が停止する点が異なる。

全ての正規言語文脈自由言語文脈依存言語帰納言語は帰納的可算言語である。

RE とその補問題 co-RE算術的階層の基盤となっている。

閉包属性

帰納的可算言語は以下の操作について閉じている。すなわち、LP を2つの帰納的可算言語としたとき、以下の言語も同様に帰納的可算言語である。

帰納的可算言語は差集合や補集合の操作については閉じていない。差集合 L\PL の補集合は帰納的可算言語となる場合もあるし、ならない場合もある。

関連項目

外部リンク

参考文献

  • Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
  • Kozen, D.C. (1997), Automata and Computability, Springer.



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

辞書ショートカット

すべての辞書の索引

「帰納的可算言語」の関連用語

帰納的可算言語のお隣キーワード
検索ランキング

   

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



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

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

©2025 GRAS Group, Inc.RSS