반복 열거 언어

이 문서에는 참고 자료, 관련 읽기 또는 외부 링크가 포함되어 있지만 인라인 인용이 부족하여 출처가 불분명합니다. 좀 더 정밀한 인용문을 도입하여 이 글의 개선에 도움을 주시기 바랍니다.(2013년 1월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

수학, 논리학, 컴퓨터 과학에서, 형식 언어는 언어의 알파벳 위에 모든 가능한 단어들의 집합에서 재귀적으로 열거할 수 있는 부분 집합인 경우, 즉 튜링 기계가 존재한다면 재귀적으로 열거할 수 있는 부분 집합이라고 불린다.l 언어의 모든 유효한 문자열을 열거합니다.

재귀적으로 열거할 수 있는 언어는 형식 언어의 촘스키 계층에서 type 0 언어로 알려져 있습니다.모든 정규, 컨텍스트프리, 컨텍스트 의존 및 재귀 언어는 재귀적으로 열거할 수 있습니다.

재귀적으로 열거할 수 있는 모든 언어의 클래스를 RE라고 합니다.

정의들

재귀적으로 열거할 수 있는 언어에는 다음 3가지 동등한 정의가 있습니다.

1. 재귀 열거 가능 언어는 언어의 알파벳에 걸쳐 가능한 모든 단어 집합에서 재귀 열거 가능 하위 집합입니다.
2. 재귀적으로 열거할 수 있는 언어는 언어의 모든 유효한 문자열을 열거하는 튜링 기계(또는 다른 계산 가능 함수)가 존재하는 형식 언어입니다.언어가 무한대인 경우 숫자 n에 대해 생성된 문자열이 n보다 작은 숫자에 대해 "이미" 생성되었는지 여부를 테스트할 수 있기 때문에 반복을 피하기 위해 제공된 열거 알고리즘을 선택할 수 있습니다.이미 생성된 경우 입력 n+1에 출력을 대신 사용합니다(반복적으로). 그러나 다시 "새로운"지 여부를 테스트합니다.
3. 재귀적으로 열거할 수 있는 언어는 튜링 기계(또는 다른 계산 가능 함수)가 존재하는 형식 언어이며, 언어 내의 문자열이 입력으로 제시될 때는 멈추고 받아들이지만 언어 내의 문자열이 제시되지 않을 때는 영원히 중지되고 거부되거나 반복될 수 있습니다.이것을 모든 경우에 튜링 머신이 정지해야 하는 재귀적 언어와 대조해 보십시오.

모든 정규, 컨텍스트프리, 컨텍스트 의존 및 재귀 언어는 재귀적으로 열거할 수 있습니다.

Post의 정리는 RE가 그 보완 co-RE와 함께 산술적 계층의 첫 번째 수준에 대응한다는 것을 보여준다.

예

정지 튜링 기계의 집합은 재귀적으로 열거할 수 있지만 재귀적이 아닙니다.실제로 튜링 머신을 실행하고 기계가 정지하면 받아들일 수 있기 때문에 재귀적으로 열거할 수 있다.한편, 그 문제는 판별할 수 없다.

재귀적이지 않은 기타 재귀 열거형 언어에는 다음과 같은 것이 있습니다.

• 통신 후 문제
• 사망률(계산 가능성 이론)
• entscheidungsproblem 문제

닫힘 속성

재귀 열거형 언어(REL)는 다음 작업으로 닫힙니다.즉, L과 P가 2개의 재귀 열거형 언어인 경우 다음 언어도 재귀 열거형 언어입니다.

• L의 클린 별 L ${\$ { $display$ $L^$ { * }
• L과 P의 연결 L${\displaystyle p}$P(\$displaystyle$ L$\circ$ P$$$)$
• $유니언{\displaystyle }$ L${\displaystyle p}$P { $display style$L \ $cup$ P$$}
• $교차로{\displaystyle }$ L$$ P { $style$ L$\cap$ P$\}.$

재귀적으로 열거 가능한 언어는 집합 차이 또는 보완 하에서는 닫히지 않습니다.설정된 차이$$L(\$displaystyle$ $$L) - P(\$displaystyle$$$P$)$는 P$(\displaystyle$ P$)$가 재귀적인 $경우{\displaystyle }$ 재귀적으로 열거됩니다.$(\displaystyle$ L$)$이 재귀 열거 가능한 경우 L$(\displaystyle$ L$)$도 재귀적인 $경우$에만 L$(\displaystyle$ L$)$의 보완이 재귀 열거됩니다.

「 」를 참조해 주세요.

• 계산적으로 열거할 수
• 재귀

레퍼런스

• Sipser, M.(1996), PWS출판사 계산이론개론
• Kozen, D.C.(1997), Automata and Computability, Springer.

외부 링크

• 복잡성 동물원: 클래스 RE
• 강의 슬라이드