G의 언어가 nil 인 문맥 자유 문법 G가있는 경우 G는 결정 가능합니까?결정할 수없는 언어를 사용하는 CFG가 있습니까?
나는 대답이 '예'라는 것을 알고 있지만, 이것을 증명하는 데 문제가 있습니다. 나의 첫 번째 생각은 G와 같은 Turing Machine의 시작 상태와 수락 상태를 나타내는 상태가 하나만 있다고 가정하는 것입니다.이 컴퓨터는 입력을 허용하지 않고 수락에 도달 했으므로 즉시 중단하고 수락합니다 상태. 이게 답할만한 대답인가, 아니면 내가 여기서 떨어져?
는 편집 : 조엘 아래 말했듯이
은 내가 설명하는 언어는 모든 문자열을 받아들입니다. 이 문제를 해결하기 위해 두 번째 기계 인 G '를 제안합니다. G '는 시작 상태 q1, 허용 상태 q2 및 거부 상태 q3의 3 가지 상태를 갖는다. q1은 G '알파벳의 모든 기호에서 q3으로 천이하고 q2도 마찬가지입니다. q1은 q2 로의 엡실론 천이를 갖는다. 따라서 G '에 공급되는 문자열에 기호가 있으면 G'가 거부됩니다. 기호가 없으면 유일한 옵션은 엡실론 전환을 승인 상태로 전환하는 것입니다. 어떻게 들리니?
EDIT : 상기 용액은 언어 L (G ')를 = { ","} 동의 입증 하였다
.
다른 용어를 사용하고있을 수 있습니다. "G의 언어가 없다"라는 말은 L (G) = {}, 즉 빈 집합을 의미합니까? 아니면 L (G) = { ""}, 즉 정확히 하나의 문자열, 즉 빈 문자열로 구성된 언어를 의미합니까? 보편성을 잃지 않고 받아들이는 상태에서 전환이 없다고 종종 가정됩니다. 따라서 수락 상태가되면 중단됩니다. 이러한 가정하에 원래의 TM은 모든 것을 허용합니다. 편집에 설명하는 TM은 L = { ""}을 수락합니다. 이것은 내가 생각하는 것입니다. 내 답변에 설명 된 TM은 아무것도 허용하지 않습니다. 즉, L = {}을 수락합니다. –
@Joel L (G) = {nil}을 의미합니다. L (G) = {}와 동일합니다. 받아들이 기 상태에 이르지 못하면 답안이 어떻게 받아 들여지는지 조금 더 설명 할 수 있습니다. (아무 것도 없기 때문에?) – Darkhydro
정의에 따르면 _M_ 컴퓨터는 _s_ 입력이 주어지면 수락 상태에 도달하면 _s_ 문자열을 허용합니다. 또한 정의상 _L (M) _은 "M에 의해 허용되는 언어"라고 불리며, _M_에 의해 받아 들여지는 모든 문자열의 집합입니다. _L (M) _은 ** 문자열 집합 **입니다. 그러나 그 세트는 사실 비어있을 수 있습니다. 기계에 승인 상태가 없으면 주어진 문자열을 허용 할 수 없습니다. 따라서 _L (M) _은 빈 집합입니다. 귀하의 G '기계는 정확하게 하나의 문자열, 즉 길이가 0 인 문자열을 받아들입니다. 따라서 _L (G ') _ = { ""}. –