재귀 언어 문서 원본 보기

{{위키데이터 속성 추적}}
'''재귀 언어'''({{llang|en|recursive language}}) 또는 '''귀납 언어'''는 [[형식 언어]]의 [[재귀 집합|재귀적]]인 부분집합이다. '''결정 가능 언어'''(decidable language)라고도 한다.

모든 재귀 언어의 모임은 [[복잡도 종류]] '''[[R (복잡도)|R]]''' 클래스와 같다. [[촘스키 위계]]에는 별도로 분류되어 있지 않다.

== 정의 ==
다음의 2가지 정의가 동치이며, 이를 만족하는 경우 '''재귀 언어'''라 한다.
* 1. 모든 가능한 형식 언어의 집합이 있을 때, 그 [[재귀 집합|재귀적]] 부분집합이다.
* 2. 다음과 같은 형식 언어: 유한 문자열을 입력받아 스트링이 해당 언어에 속하면 accept 후 정지하고 그렇지 않으면 reject 후 정지하는 [[튜링기계]]가 있다. 이 튜링기계는 항상 정지하므로, 이를 결정기계(decider)이라 하며 이는 재귀 언어를 결정(decide)한다.

== 폐포 성질 ==
재귀 언어들은 다음 연산에 대해 [[폐포 (수학)|닫혀있다]]. 즉 두 재귀 언어 <math>L</math>과 <math>P</math>에 대하여 다음 언어도 재귀적이다:
* [[클레이니 스타]] <math>L^*</math>
* 연결 <math>L \circ P</math>
* 합집합 <math>L \cup P</math>
* 교집합 <math>L \cap P</math>
* <math>L</math>의 여집합
* 차집합 <math>L - P</math>

== 같이 보기 ==
* [[재귀 열거 언어]]
* [[재귀 집합]]
* [[재귀]]

{{형식 언어 및 형식 문법}}

[[분류:형식 언어]]
[[분류:계산 가능성 이론]]
[[분류:계산 이론]]
[[분류:앨런 튜링]]
[[분류:재귀]]