알파벳 및 공식 문법 및 언어에 대한 도전

Question

A가 유한이거나 일대일 자연수로 매핑되는 경우 집합 A가 셀 수있는 것으로 알고 있습니다.

ALPH가 임의의 유한 알파벳이라고 가정합니다.

A) ALPH에 각각 임의의 언어 가산 근로있다 :

나는 나의 추론을 요약한다.

B) ALPH 모든 언어의 세트가 가산 근로이다 (나는 이것이 사실 생각). (나는이 거짓이라고 생각)

C) ALPH에 각각 임의의 언어에 대해 우리가 생식 형식적인 문법을 가지고있다. (나는 이것이 거짓이라고 생각한다)

d) 공식 문법에 의해 생성 될 수있는 ALPH의 각 임의의 언어는 재귀 적이다. (나는 이것이 사실이라고 생각한다)

누구나 나를 도울 수 있고, 아마도 나를 고칠 수 있을까?

Answer 1

일반성을 잃지 않고 ALPH가 단지 {0,1}이라고 가정 할 수 있습니다. (물론 다른 유한 언어도 집합 {0,1}을 사용하여 인코딩 할 수 있습니다.) 언어 L에 의해 ALPH *의 임의의 부분 집합을 의도한다고 가정하면, L은 {0,1} *의 임의의 부분 집합이라고 가정 할 수 있습니다.

S = {0,1} *이라고하자.

a) 집합 S는 셀 수 있습니다. L은 S의 서브 세트이므로 L은 셀 수 있습니다.

b) S의 모든 언어 집합은 S의 powerset이며, 실수의 수와 1-1로 대응할 수 있습니다. 그러므로, 셀 수 없다.

c) 나는 이것이 거짓이며 귀하의 가정에 동의한다고 생각합니다. 그러나 그것은 '생성적인 형식 문법'에 대한 귀하의 정의에 달려 있습니다. 문법의 개별 규칙을 결정할 수없는 공식 문법을 허용하거나 무한 생성 규칙을 허용하는 경우 이는 명확하지 않게됩니다. 'generative formal grammar'의 모음이 열거 될 수있는 'generative formal grammar'에 대한 특정 정의에 대해서는 물론 대답이 거짓입니다.

d) 일반적으로이 질문에 대한 대답은 입니다. 문맥 자유 언어에 해당하는 공식 문법으로 자신을 제한한다면, 물론 당신의 대답은 사실입니다. 그러나, 고려하십시오 http://en.wikipedia.org/wiki/Post_correspondence_problem 문제는 결정할 수 없다, 그러나 발생 규칙은 아주 명확하다.