재귀적 언어

이 문서에는 인라인 따옴표가 포함되어 있지만 형식이 올바르지 않습니다. 그것들을 수정하여 이 글을 개선해 주세요. 상위 가상 참조가 더 이상 사용되지 않습니다. 단축 각주로 변환하십시오.(2022년 6월) (이 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다)

수학, 논리학, 컴퓨터 과학에서, 형식 언어(고정 알파벳에서 가져온 기호의 유한 계열 집합)는 언어의 알파벳 위에 가능한 모든 유한 계열 집합의 재귀적 부분 집합일 경우 재귀적이라 불린다.마찬가지로, 입력으로 주어졌을 때, 기호의 유한 시퀀스가 주어졌을 때, 그것이 언어에 속하면 받아들이고 그렇지 않으면 그것을 거부하는 총 튜링 기계(모든 주어진 입력에 대해 멈추는 튜링 기계)가 존재한다면 공식 언어는 재귀적이다.재귀 언어는 결정 가능 언어라고도 합니다.

결정성의 개념은 다른 계산 모델로 확장될 수 있다.예를 들어, 비결정론적 튜링 기계에서 결정 가능한 언어에 대해 말할 수 있다.그러므로 모호성이 가능할 때마다, "재귀적 언어"에 사용되는 동의어는 단순히 결정 가능하기 보다는 튜링 결정 가능 언어이다.

모든 재귀 언어의 클래스는 종종 R이라고 불리지만 이 이름은 클래스 RP에도 사용됩니다.

이러한 유형의 언어는 촘스키 계층(촘스키 1959)에서 정의되지 않았습니다.모든 재귀적 언어도 재귀적으로 열거할 수 있습니다.문맥이 없는 일반 언어 및 문맥 의존 언어는 모두 재귀적입니다.

정의들

재귀 언어의 개념에는 다음과 같은 두 가지 주요 정의가 있습니다.

1. 재귀적 형식 언어는 언어의 알파벳 위에 있는 가능한 모든 단어 집합의 재귀적 하위 집합입니다.
2. 재귀 언어는 튜링 기계가 존재하는 형식 언어입니다. 튜링 기계는 유한한 입력 문자열이 제시되면 해당 문자열이 언어 내에 있으면 정지하고 받아들이며, 그렇지 않으면 정지하고 거부합니다.튜링 기계는 항상 멈춥니다: 그것은 결정자로 알려져 있으며 재귀 언어를 결정한다고 합니다.

두 번째 정의에 따르면, 모든 입력에서 종료되는 결정 문제를 위한 알고리즘을 제시함으로써 결정 가능한 것으로 나타낼 수 있다.결정할 수 없는 문제는 결정할 수 없는 문제이다.

예

위에서 설명한 바와 같이 컨텍스트에 민감한 모든 언어는 재귀적입니다.따라서, 재귀 언어의 간단한 예는 집합 L={abc, aabbcc, aaabbcc, ...이다.}; 좀 더 형식적으로 말하면 세트

${\displaystyle L=\{,w\in\{a,b,c\}^{*}\mid w=a^{n}b^{n}c^{n}{\mbox{일부}}n\geq 1,\}}}}$

는 컨텍스트에 의존하기 때문에 재귀적입니다.

문맥에 구애받지 않는 결정 가능한 언어의 예는 설명하기가 더 어렵습니다.그러한 예로서, 수학 논리에 대한 약간의 지식이 필요하다: 프리버거 산수는 덧셈을 포함한 자연수의 1차 이론이다.Presburger 산술의 잘 형성된 공식 집합은 문맥이 없는 반면 Presburger 산술의 참 스테이트먼트 집합을 받아들이는 모든 결정론적 튜링 기계는 최소 $(\$ 2$^{2^{$cn$\}\})$의 최악의 실행 시간을 일정 c>0(Fischer & Rabin 1974)에 대해 $갖는다{\displaystyle {\mathrm{}}^{}}$.여기서 n은 주어진 공식의 길이를 나타낸다.컨텍스트에 민감한 모든 언어는 선형 경계 자동화에 의해 수용될 수$있으며,$ 그러한 자동화는 일부^{[citation needed]} 상수$c$에 대해 $최악$의 실행 시간을 가진 결정론적 튜링 기계에 의해 시뮬레이션될 수 있기 때문에 Presburger 산술의 유효한 공식 세트는 컨텍스트에 민감하지 않습니다.긍정적인 측면에서는, 프레스버거 산술에서 참 공식 집합을 결정하는 결정론적 튜링 기계가 n에서 최대 3배 기하급수적으로 작동한다고 알려져 있다(Oppen 1978.따라서 이는 결정 가능하지만 문맥에 구애받지 않는 언어의 예입니다.

닫힘 속성

재귀 언어는 다음 작업에서 닫힙니다.즉, L과 P가 2개의 재귀 언어인 경우 다음 언어도 재귀 언어입니다.

• 더 클린 $스타{\displaystyle {}^{}}$ L$★(\$ L$^{*})$
• e-free 동형 하의 이미지 【L】
• $연결{\displaystyle }$ L${\displaystyle p}$P \ $displaystyle$L \ $circ$ P$$}
• $유니언{\displaystyle }$ L${\displaystyle p}$P { $display L$\ $cup$ P$$}
• $교차로{\displaystyle }$ L$$ P { $displaystyle$L \ $cap$ P$$}
• $\displaystyle$L의 보완물
• $설정차이{\displaystyle }$L$$- ${\displaystyle P}$ { $displaystyle$ L - P$$}

마지막 속성은 집합의 차이를 교집합과 보완의 관점에서 표현할 수 있다는 사실에서 비롯된다.

「 」를 참조해 주세요.

• 반복 열거 언어
• 계산 가능한 집합
• 재귀

레퍼런스

• Michael Sipser (1997). "Decidability". Introduction to the Theory of Computation. PWS Publishing. pp. 151–170. ISBN 978-0-534-94728-6.
• Chomsky, Noam (1959). "On certain formal properties of grammars". Information and Control. 2 (2): 137–167. doi:10.1016/S0019-9958(59)90362-6.
• Fischer, Michael J.; Rabin, Michael O. (1974). "Super-Exponential Complexity of Presburger Arithmetic". Proceedings of the SIAM-AMS Symposium in Applied Mathematics. 7: 27–41.
• Oppen, Derek C. (1978). "A 2^22pn Upper Bound on the Complexity of Presburger Arithmetic". J. Comput. Syst. Sci. 16 (3): 323–332. doi:10.1016/0022-0000(78)90021-1.