재귀 열거 언어
위키백과 ― 우리 모두의 백과사전.
수학의논리학과 전산학에서 재귀 열거 언어는 형식언어의 한 종류며 또한 부분결정성언어 또는 튜링수리성언어라고 불린다.형식언어의 촘스키 위계에 따른 type-0언어로 알려져 있다.모든 귀납적가산언어를 RE라고 부른다.
[편집] 정의
재귀 열거 언어의 개념에 관한 세개의 동등한 주요 정리가 존재한다.
- 재귀 열거 언어는 언어의 문자로 만들 수 있는 재귀 열거 집합의 부분집합이다.
- 재귀 열거 언어는 언어의 모든 옳은 문자열을 세는 튜링 기계 (또는 다른 계산 가능 함수)가 존재하는 형식언어이다. 주목할 것은 만약 언어가 무한하다면 제공된 가산알고리듬을 고를 수 있어 반복을 피할 수 있는데 우리가 숫자 n으로 산출되어진 문자열이 이미 더 작은 숫자 n에서 산출됬는지 확인 할 수 있기때문이다. 만약 이미 산출된 결과라면, 출력을 입력 n+1으로 대신 (귀납적으로)사용하지만, 반복해서 새로운지 확인이 필요하다.
- 재귀 열거 언어는 어떤 언어의 문자열이 입력으로 주어질때 서고 승인하지만 언어에 속하지 않은 문자열이 주어질때 정지하고 거절하는 튜링 기계 (또는 다른 계산 가능 함수)이 존재하는 형식언어이다. 튜링머신이 정지하는 필요한 모든 경우에 이것을 재귀 언어 와 대조한다.
모든 정규언어, 문맥자유언어, 문맥의존언어,재귀 언어는 귀납적가산언어이다. RE, 그것의 보완물 co-RE는 산술적계층의 기반이 되고 있다.
[편집] 닫힘특성
재귀 열거 언어는 다은 과정에 대해 닫혀있다. 만약L과P가 귀납적가산언어라면 다음의 언어는 재귀 열거 언어이다.
주목할 것은 재귀 열거 언어는 차집합이나 여집합에서는 닫혀있지 않다는 것이다. 차집합L\P는 귀납적 가산언어일수도 아닐 수 도 있다. 만약 L이 귀납적 가산 언어라면, L의 여집합은 재귀 열거 언어인 경우에만 L이 또한 귀납적이다.
[편집] 같이 보기
- 재귀 언어.
