사전 식 순서로 인식 가능한 언어를 열거하십시오.

Question

Turing 인식 가능한 언어도 열거 가능합니다.

그러나 열거자가 Turing 인식 가능한 언어를 사전 식 순서로 "인쇄"할 수 있습니까?

Answer 1

아니요. 가능하다고 가정합니다. 그러면 언어는 다음과 같이 결정될 수 있습니다.

1. 허용되는 모든 문자열을 순서대로 나열합니다.
2. 찾고있는 문자열보다 사전 식 순서가 큰 문자열을 나열하는 경우 거부를 중지하십시오.
3. 찾고있는 문자열을 나열하면 accept가 허용됩니다.

이 결국 단지 유한 한 많은 열거 된 문자열이 작은 사전 편찬 순서로 존재 주어진 입력 문자열에 대한 이후 모든 입력 문자열을 종료합니다. 그것은 당신의 목표 문자열을 찾지 못하면 항상 거부를 멈출 것이고, 그렇다면 받아들이는 것을 항상 중단 할 것입니다. 문자열을 나열한 덕분에 문자열이 있어야하는 위치를 알 수 있으므로 문자열을 놓친 것에 대해 걱정할 필요가 없습니다.

결정할 수없는 열거 가능한 언어가 있다는 것을 알고 있으므로 순서대로 열거 가능한 언어를 열거 할 수 없어야합니다.