특정 구문이있는 문자열이 포함 된 언어에 대한 미확인 가능성을 증명합니다.

Question

우리는 다음과 같은 문제가 있다고 가정합니다.

$$ \ mathcal {l} _1={\ langle \ mathcal {m} \ rangle |\ MathCal {m} \ \ text {turing machine 및 $ \ mathcal {l} (\ mathcal {m}) $는 정확히 세 개의 zeros} \} $$

가있는 문자열을 포함합니다.

$ \ mathcal {l} _1 $ 이 undecidable임을 증명하고 싶습니다.나는 일반적으로 쌀의 정리를 사용하여 언어가 미확인이 될 수 없다는 것을 증명할 것입니다. 그러나 현재의 경우에는 언어의 의미 론적 특성을 다루지는 않지만 구문을 사용하지 않습니다.우리가 언어의 건설을 기반으로 증명 해야하는 경우, 프로세스는 어떻게 쌀의 정리로 입증되는 것과 어떻게 생겼을 것입니까?

Answer 1

언어의 의미 론적 자산과 ok 에서

$ c= {l | \ text {정확히 3 개의 0이있는 문자열이 있습니다 \} $

so, $ l_1={ | m \ text {turing machine 및} l (m) \ \ k \ \ in c \} $ $ C \ Neq \ EmptySet $ 및 $ C $ 은 모든 언어가 아닙니다. 그 다음 쌀의 정리에 의해 $ L_1 \ NOTIN R $ .