Recursively enumerable languageとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > Recursively enumerable languageの意味・解説 

帰納的可算言語

(Recursively enumerable language から転送)

出典: フリー百科事典『ウィキペディア(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.

「Recursively enumerable language」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


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

辞書ショートカット

すべての辞書の索引

「Recursively enumerable language」の関連用語

Recursively enumerable languageのお隣キーワード
検索ランキング

   

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



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

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの帰納的可算言語 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS