|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 帰納 ： [きのう] (n,vs) inductive ・ 言 ： [げん] 【名詞】 1. word 2. remark 3. statement ・ 語 ： [ご] 1. (n,n-suf) language 2. word
帰納言語（きのうげんご、）は、数学・論理学・計算機科学における形式言語の一種である。決定性言語(Decidable Language)、チューリング決定性言語(Turing-decidable Language)とも呼ぶ。全ての帰納言語の属する複雑性クラスをRと呼ぶが、RPクラスを Rと呼ぶこともある。 このクラスの言語はチョムスキー階層では定義されていない（Chomsky 1959）。 == 定義 == 帰納言語の定義には以下の2つの等価な定義がある。 # 帰納言語は、形式言語のアルファベットにおける全ての単語の集合のうちの帰納的部分集合である。 # 帰納言語は、その言語を受容するチューリングマシンがあったとき、その言語に属する文字列を入力したとき常に停止して受容し、属さない文字列を入力したとき常に停止して拒絶するような言語である。つまり、このチューリングマシンは常に停止する。このようなチューリング機械を decider と呼び、帰納言語を決定（decide）する。 全ての帰納言語は帰納的に枚挙可能である。全ての正規言語、文脈自由言語、文脈依存言語は帰納言語である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「帰納言語」の詳細全文を読む スポンサード リンク
|