|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 帰納 ： [きのう] (n,vs) inductive ・ 帰納的 ： [きのうてき] 1. (adj-na,n) inductive 2. recursive ・ 的 ： [まと, てき] 【名詞】 1. mark 2. target ・ 可 ： [か] 1. (n,n-suf) passable ・ 言 ： [げん] 【名詞】 1. word 2. remark 3. statement ・ 語 ： [ご] 1. (n,n-suf) language 2. word
帰納的可算言語（きのうてきかさんげんご、）は、数学・論理学・計算機科学における形式言語の一種である。部分決定性言語（Partially Decidable Language）、チューリング受理性言語（Turing-recognizable Language）とも呼ぶ。形式言語のチョムスキー階層におけるタイプ-0言語に相当する。全ての帰納的可算言語は複雑性クラス RE に属する。 == 定義 == 帰納的可算言語には以下の3つの等価な定義がある。 # 帰納的可算言語は、形式言語のアルファベットから生成可能な全ての単語の集合のうち、帰納的可算な部分集合である。 # 帰納的可算言語は、その言語に含まれる全文字列を数え上げるチューリング機械（または計算可能関数）が存在する形式言語である。言語が無限である場合、同じ文字列が現れないようなアルゴリズムが必要である。すなわち、''n'' 番目の文字列が以前に出現しているかどうかを判定し、もし既出であったら ''n+1'' 番目の文字列を代わりに出力する。ただし、その ''n+1'' 番目の文字列も既出でないか確認が必要である。 # 帰納的可算言語は、入力された文字列がその言語に含まれる場合にそれを受理して停止するチューリング機械（または計算可能関数）が存在する形式言語である。ただし、入力された文字列がその言語に含まれない場合、停止して拒絶するかもしれないし、無限ループするかもしれない。帰納言語は常にチューリング機械が停止する点が異なる。 全ての正規言語、文脈自由言語、文脈依存言語、帰納言語は帰納的可算言語である。 RE とその補問題 co-RE は算術的階層の基盤となっている。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「帰納的可算言語」の詳細全文を読む スポンサード リンク
|