재귀 언어

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

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

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

정의[편집]

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

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

폐포 성질[편집]

재귀 언어들은 다음 연산에 대해 닫혀있다. 즉 두 재귀 언어 에 대하여 다음 언어도 재귀적이다:

  • 클레이니 스타
  • 연결
  • 합집합
  • 교집합
  • 의 여집합
  • 차집합

같이 보기[편집]