재귀 열거 언어 문서 원본 보기

{{위키데이터 속성 추적}}
'''재귀적 열거 가능 언어'''(再歸的列擧可能言語, {{llang|en|Recursively enumerable language}}, 귀납적 가산 언어(歸納的可算言語)), '''부분 결정성 언어''' 또는 '''튜링 수리성 언어'''는 [[계산 이론]]과 [[수리논리학]]에서 다루는 [[형식 언어]]의 종류로, 문자열의 집합의 [[재귀 열거 집합|재귀 열거인 부분집합]]이다. [[촘스키 위계]]의 '''type-0 언어'''이기도 하다. 재귀 열거 언어의 모임을 '''[[RE (복잡도)|RE]]'''라고 한다.

== 정의 ==
재귀 열거 언어의 개념에 관한 세개의 동등한 주요 정리가 존재한다.

# 재귀 열거 언어는 [[형식언어|언어]]의 [[문자]]로 만들 수 있는 [[재귀 열거 집합]]의 [[부분집합]]이다.
# 재귀 열거 언어는 언어의 모든 옳은 문자열을 세는 [[튜링 기계]] (또는 다른 계산 가능 함수)가 존재하는 형식언어이다. 주목할 것은 만약 언어가 [[무한]]하다면 제공된 가산알고리듬을 고를 수 있어 반복을 피할 수 있는데 우리가 숫자 ''n''으로 산출된 문자열이 이미 더 작은 숫자 ''n''에서 산출됐는지 확인할 수 있기 때문이다. 만약 이미 산출된 결과라면, 출력을 입력 ''n+1''으로 대신 (귀납적으로)사용하지만, 반복해서 새로운지 확인이 필요하다.
# 재귀 열거 언어는 어떤 언어의 [[문자열]]이 입력으로 주어질때 서고 승인하지만 언어에 속하지 않은 문자열이 주어질때 정지하고 거절하는 [[튜링 기계]] (또는 다른 계산 가능 함수)이 존재하는 형식언어이다. 튜링머신이 정지하는 필요한 모든 경우에 이것을 [[재귀 언어]]와 대조한다.

모든 [[정규 언어]], [[문맥 자유 언어]], [[문맥 의존 언어]], [[재귀 언어]]는 재귀 열거 언어이다. 

'''[[RE (복잡도)|RE]]''', 그것의 보완물 [[co-RE]]는 [[산술적 위계]]의 기반이 되고 있다.

== 닫힘특성 ==

재귀 열거 언어는 다음 과정에 대해 [[닫힘 (수학)|닫혀있다]]. 만약 ''L'' 과 ''P'' 가 재귀 열거 언어라면 다음의 언어는 재귀 열거 언어이다.
* ''L''의 [[클레이니 스타]](Kleene star): <math>L^*</math>
* ''L''과''P''의 [[연결]]: <math>L \circ P\,</math>
* ''L''과''P''의 [[합집합]]: <math>L \cup P\,</math>
* ''L''과''P''의 [[교집합]]: <math>L \cap P\,</math>

주목할 것은 재귀 열거 언어는 차집합이나 여집합에서는 닫혀있지 않다는 것이다. 차집합 ''L''\''P''는 재귀 열거 언어일 수도 아닐 수도 있다. 만약 ''L''이 재귀 열거 언어라면, ''L''의 여집합은 재귀 열거 언어인 경우에만 ''L''이 또한 귀납적이다.

== 같이 보기 ==
* [[재귀 언어]]

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

[[분류:형식 언어]]
[[분류:계산 이론]]
[[분류:앨런 튜링]]