帰納言語

帰納言語（きのうげんご、）は、数学・論理学・計算機科学における形式言語の一種である。決定性言語(Decidable Language)、チューリング決定性言語(Turing-decidable Language)とも呼ぶ。全ての帰納言語の属する複雑性クラスをRと呼ぶが、RPクラスを Rと呼ぶこともある。
このクラスの言語はチョムスキー階層では定義されていない（Chomsky 1959）。
定義.
帰納言語の定義には以下の2つの等価な定義がある。
全ての帰納言語は帰納的に枚挙可能である。全ての正規言語、文脈自由言語、文脈依存言語は帰納言語である。
閉包属性.
帰納言語は以下の操作について閉じている。すなわち、"L" と "P" を2つの帰納言語としたとき、以下の言語も同様に帰納言語である。
最後の属性は、差集合が和集合と共通部分から求められることから導出される。