帰納言語

帰納言語（きのうげんご、英: Recursive language）は、数学・論理学・計算機科学における形式言語の一種である。決定性言語(Decidable Language)、チューリング決定性言語(Turing-decidable Language)とも呼ぶ。全ての帰納言語の属する複雑性クラスをRと呼ぶが、RPクラスを Rと呼ぶこともある。

このクラスの言語はチョムスキー階層では定義されていない（Chomsky 1959）。

定義

帰納言語の定義には以下の2つの等価な定義がある。

1. 帰納言語は、形式言語のアルファベットにおける全ての単語の集合のうちの帰納的部分集合である。
2. 帰納言語は、その言語を受容するチューリングマシンがあったとき、その言語に属する文字列を入力したとき常に停止して受容し、属さない文字列を入力したとき常に停止して拒絶するような言語である。つまり、このチューリングマシンは常に停止する。このようなチューリング機械を decider と呼び、帰納言語を決定（decide）する。

全ての帰納言語は帰納的に枚挙可能である。全ての正規言語、文脈自由言語、文脈依存言語は帰納言語である。

閉包属性

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

• Lのクリーネ閉包 $L^{*}$
• Lの準同型写像 φ(L)
• L と P の連結 $L\circ P$
• 和集合 $L\cup P$
• 共通部分 $L\cap P$
• L の補集合
• 差集合 $L-P$

最後の属性は、差集合が和集合と共通部分から求められることから導出される。

参考文献

• Michael Sipser (1997年). “Decidability”. Introduction to the Theory of Computation. PWS Publishing. pp. 151–170. ISBN 0-534-94728-X 
• Chomsky, Noam (1959年). “On certain formal properties of grammars”. Information and Control 2 (2): 137–167. 

関連項目

• 帰納的可算言語
• 再帰呼び出し
• 再帰的頭字語