재귀 언어

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

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

정의

다음의 2가지 정의가 동치이며, 이를 만족하는 경우 재귀 언어라 한다.

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

폐포 성질

재귀 언어들은 다음 연산에 대해 닫혀있다. 즉 두 재귀 언어 ${\displaystyle L}$과 ${\displaystyle P}$에 대하여 다음 언어도 재귀적이다:

• 클레이니 스타 ${\displaystyle L^{*}}$
• 연결 ${\displaystyle L\circ P}$
• 합집합 ${\displaystyle L\cup P}$
• 교집합 ${\displaystyle L\cap P}$
• ${\displaystyle L}$의 여집합
• 차집합 ${\displaystyle L-P}$

같이 보기

• 재귀 열거 언어
• 재귀 집합
• 재귀