帰納言語のソースを表示

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

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

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

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

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

== 閉包属性 ==
帰納言語は以下の操作について[[生成 (数学)|閉じている]]。すなわち、''L'' と ''P'' を2つの帰納言語としたとき、以下の言語も同様に帰納言語である。
* ''L''の[[クリーネ閉包]] <math>L^*</math>
* ''L''の[[準同型]]写像 φ(L)
* ''L'' と ''P'' の連結 <math>L \circ P</math>
* [[合併 (集合論)|和集合]] <math>L \cup P</math>
* [[共通部分 (数学)|共通部分]] <math>L \cap P</math>
* ''L'' の補集合
* [[差集合]] <math>L - P</math>

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

== 参考文献 ==
* {{cite book|author = Michael Sipser | date = 1997年 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | chapter = Decidability | pages = 151–170 | id = ISBN 0-534-94728-X}}
* {{cite journal | last = Chomsky | first = Noam | date = 1959年 | title = On certain formal properties of grammars | journal = Information and Control | volume = 2 | issue = 2 | pages = 137–167}}

== 関連項目 ==
*[[帰納的可算言語]]
*[[再帰呼び出し]]
*[[再帰的頭字語]]

{{DEFAULTSORT:きのうけんこ}}
[[Category:数理論理学]]
[[Category:形式言語]]
[[Category:計算理論]]
[[Category:再帰]]
[[Category:数学に関する記事]]