재귀 언어

재귀 언어() 또는 귀납 언어는 형식 언어의 재귀적인 부분집합이다. 결정 가능 언어(decidable language)라고도 한다.

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

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

 폐포 성질 
재귀 언어들은 다음 연산에 대해 닫혀있다. 즉 두 재귀 언어 과 에 대하여 다음 언어도 재귀적이다:
 클레이니 스타 
 연결 
 합집합 
 교집합 
 의 여집합
 차집합 

 같이 보기 
 재귀 열거 언어
 재귀 집합
 재귀

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