결정할 수없는 언어를 사용하는 CFG가 있습니까?

Question

G의 언어가 nil 인 문맥 자유 문법 G가있는 경우 G는 결정 가능합니까?

나는 대답이 '예'라는 것을 알고 있지만, 이것을 증명하는 데 문제가 있습니다. 나의 첫 번째 생각은 G와 같은 Turing Machine의 시작 상태와 수락 상태를 나타내는 상태가 하나만 있다고 가정하는 것입니다.이 컴퓨터는 입력을 허용하지 않고 수락에 도달 했으므로 즉시 중단하고 수락합니다 상태. 이게 답할만한 대답인가, 아니면 내가 여기서 떨어져?

는 편집 : 조엘 아래 말했듯이

은 내가 설명하는 언어는 모든 문자열을 받아들입니다. 이 문제를 해결하기 위해 두 번째 기계 인 G '를 제안합니다. G '는 시작 상태 q1, 허용 상태 q2 및 거부 상태 q3의 3 가지 상태를 갖는다. q1은 G '알파벳의 모든 기호에서 q3으로 천이하고 q2도 마찬가지입니다. q1은 q2 로의 엡실론 천이를 갖는다. 따라서 G '에 공급되는 문자열에 기호가 있으면 G'가 거부됩니다. 기호가 없으면 유일한 옵션은 엡실론 전환을 승인 상태로 전환하는 것입니다. 어떻게 들리니?

EDIT : 상기 용액은 언어 L (G ')를 = { ","} 동의 입증 하였다

.

Answer 1

당신이 말했듯이 대답은 '예'입니다. 일반적인 증거는 CFG G이 주어지면 TM 문법을 사용하여 TM을 쉽게 파생시킬 수 있다는 것입니다. 그러나 빈 언어에 대한 간단한 증거를 찾고 있습니다. (이 경우 CFG를 가지고 있다는 사실은 부적절합니다.)

주어진 언어 L에 대해 항상 중단되는 TM을 구성 할 수있는 경우 올바른 길을 걷고 있습니다. 그렇다면 L은 결정할 수 있습니다. 그러나 설명하는 기계는 실제로 모든 문자열, 즉 알파벳에 대해 가능한 모든 문자열로 구성된 언어를 허용합니다. 시작 상태가 수락 상태이기도하면 튜링 기계가 시작될 때 즉시 수락 할 것이기 때문입니다. 받아들이 기 위해 전체 입력 문자열 (또는 그 일부)을 읽을 필요는 없습니다.

아무 것도 받아들이지 않는 TM을 정의하려면 수락 상태 집합을 비워 둡니다. 기계가 항상 정지되도록하려면 전환 기능도 비어있을 수 있습니다.