재귀 언어

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. 정의 1: 재귀적 부분집합
- 2.2. 정의 2: 결정 가능한 튜링 기계
3. 예시
4. 폐포 성질
참조

1. 개요

재귀 언어는 형식 언어의 한 종류로, 튜링 머신이 입력을 받아 해당 언어에 속하는지 여부를 결정할 수 있는 언어이다. 재귀 언어는 재귀 집합의 부분집합으로 정의되거나, 튜링 머신이 입력을 받아 언어에 속하면 accept, 그렇지 않으면 reject하고 항상 정지하는 형식 언어로 정의될 수 있다. 모든 정규 언어, 문맥 자유 언어, 문맥 의존 언어는 재귀 언어에 속하며, 재귀 언어는 클레이니 스타, ε-프리 준동형 사상, 연결, 합집합, 교집합, 여집합, 차집합 연산에 대해 닫혀있다.

더 읽어볼만한 페이지

앨런 튜링 - 튜링 테스트
튜링 테스트는 앨런 튜링이 제안한 기준으로, 기계가 인간과 구별할 수 없을 정도로 행동하는지 판별하며, 뢰브너 상 등을 통해 실현 가능성과 한계에 대한 논쟁이 지속되고 있고, 유진 구스트만, LaMDA, ChatGPT 등이 테스트 통과 또는 자의식 논란을 일으키고 있다.
앨런 튜링 - 이미테이션 게임
제2차 세계 대전 당시 독일군의 에니그마 암호 해독에 결정적인 역할을 한 수학자 앨런 튜링의 실화를 바탕으로, 암호 해독팀이 암호 해독 기계 "봄베"를 개발하는 과정과 전후 동성애 사실이 밝혀져 박해받는 그의 비극적인 삶을 그린 2014년 영화이다.
재귀 - 무한 루프
무한 루프는 컴퓨터 프로그램에서 루프가 종료되지 않고 무한히 반복되는 현상으로, 프로그램 오류나 의도적인 경우에 발생하며 시스템 응답 불능을 초래하거나 특정 상황에서 사용되기도 한다.
재귀 - 점화식
점화식은 수열의 각 항을 이전 항들의 함수로 표현하는 방정식으로, 피보나치 수열, 로지스틱 맵, 이항 계수 등의 예시가 있으며, 선형대수학이나 Z변환 등을 이용하여 풀고 다양한 분야에 응용된다.
계산 이론 - 튜링 완전
튜링 완전은 계산 이론에서 시스템이 튜링 기계와 동등한 계산 능력을 갖춰 튜링 기계가 계산할 수 있는 모든 함수를 계산하고 범용 튜링 기계를 시뮬레이션할 수 있음을 의미하며, 튜링 동등이라고도 한다.
계산 이론 - 디지털 물리학
디지털 물리학은 우주를 거대한 디지털 컴퓨터로 보고 정보 이론, 통계 역학, 양자역학 등을 융합하여 우주의 작동 방식을 디지털 계산 과정으로 설명하려는 이론적 관점이다.

재귀 언어

2. 정의

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

모든 가능한 형식 언어의 집합에서 재귀적 부분집합이다.
유한 문자열을 입력받아 문자열이 해당 언어에 속하면 정지하여 수락하고, 그렇지 않으면 정지하여 거부하는 튜링 기계가 있다. 이 튜링 기계는 항상 정지하므로, 결정 기계라고 하며 재귀 언어를 결정한다.

모든 정규 언어, 문맥 자유 언어, 문맥 의존 언어는 재귀 언어이다.

2. 1. 정의 1: 재귀적 부분집합

재귀 언어는 모든 가능한 형식 언어의 집합에서 재귀적 부분집합이다.

2. 2. 정의 2: 결정 가능한 튜링 기계

유한 문자열을 입력받아 해당 문자열이 언어에 속하면 정지하여 수락하고, 그렇지 않으면 정지하여 거부하는 튜링 기계가 존재하는 형식 언어가 재귀 언어이다. 이 튜링 기계는 항상 정지하므로, 결정자라고 하며 재귀 언어를 '결정'한다고 한다.

두 번째 정의에 따르면 모든 결정 문제는 모든 입력에 대해 종료되는 알고리즘을 제시함으로써 결정 가능함을 보일 수 있다. 결정 불가능 문제는 결정할 수 없는 문제이다.

3. 예시

모든 문맥 의존 언어는 재귀적이다. 따라서 재귀 언어의 간단한 예는 집합 ''L={abc, aabbcc, aaabbbccc, ...}''이다. 더 공식적으로 표현하면 다음과 같다.

: $L=\{\,w \in \{a,b,c\}^* \mid w=a^nb^nc^n \mbox{ for some } n\ge 1 \,\}$

이는 문맥 의존적이므로 재귀적이다.

문맥 의존적이지 않은 결정 가능한 언어의 예는 설명하기 더 어렵다. 이를 위해서는 수학적 논리에 대한 어느 정도의 지식이 필요하다. 프레스버거 산술은 덧셈(곱셈은 제외)이 있는 자연수의 일차 이론이다. 프레스버거 산술의 잘 구성된 공식 집합은 문맥 자유 언어이지만, 프레스버거 산술의 참된 명제 집합을 수용하는 모든 결정적 튜링 기계는 어떤 상수 ''c''>0에 대해 최악의 경우 $2^{2^{cn}}$ 의 실행 시간을 갖는다. 여기서 ''n''은 주어진 공식의 길이를 나타낸다. 모든 문맥 의존 언어는 선형 유계 오토마타에 의해 수용될 수 있으며, 이러한 오토마타는 어떤 상수에 대해 최악의 경우 $c^n$ 의 실행 시간을 갖는 결정적 튜링 기계로 시뮬레이션될 수 있으므로, 프레스버거 산술의 유효한 공식 집합은 문맥 의존적이지 않다. 긍정적인 측면에서, 프레스버거 산술의 참된 공식 집합을 결정하는, ''n''에 대해 최대 3중 지수 시간 내에 실행되는 결정적 튜링 기계가 있다는 것이 알려져 있다. 따라서 이는 결정 가능하지만 문맥 의존적이지 않은 언어의 예이다.

4. 폐포 성질

재귀 언어는 다음 연산에 대해 닫혀있다. 즉, 두 재귀 언어 $L$ 과 $P$ 에 대하여 다음 연산 결과도 재귀 언어이다:

클레이니 스타 $L^*$
ε-프리 준동형 사상 φ에 따른 이미지 φ(L)
연결 $L \circ P$
합집합 $L \cup P$
교집합 $L \cap P$
$L$ 의 여집합
차집합 $L - P$

4. 1. 클레이니 스타

재귀 언어는 클레이니 스타 연산에 대해 닫혀있다.

4. 2. ε-프리 준동형 사상

''L''과 ''P''가 두 개의 재귀 언어인 경우, ε-프리 준동형 사상 φ에 따른 이미지 φ(L) 또한 재귀적이다.

4. 3. 연결

닫혀있는 재귀 언어 ''L''과 ''P''에 대하여, 다음 언어 또한 재귀적이다.

$L \circ P$ 연결

4. 4. 합집합

재귀 언어 ''L''과 ''P''가 있을 때, 다음 언어 역시 재귀적이다.

합집합 $L \cup P$

4. 5. 교집합

닫혀 있는 재귀 언어 ''L''과 ''P''가 있을 때, ''L''과 ''P''의 교집합

L \cap P

역시 재귀적이다.

4. 6. 여집합

재귀 언어는 다음 연산에 대해 닫혀있다. 즉, ''L''과 ''P''가 두 개의 재귀 언어인 경우, 다음 언어 또한 재귀적이다.

$L$ 의 여집합

마지막 속성은 차집합이 교집합과 여집합으로 표현될 수 있다는 사실에서 비롯된다.

4. 7. 차집합

두 재귀 언어 ''L''과 ''P''의 차집합

L - P

는 재귀적이다. 이는 차집합이 교집합과 여집합으로 표현될 수 있기 때문이다.

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com