이 언어는 정규 언어인가요?

Question

알파벳 {0,1}에 대해 {4^(w⋅g)34^(g)|w,g∈NAT}라는 언어가 있습니다.

이 언어가 인식 가능한지, 결정 가능한지, 문맥이 없는지, 규칙적인지, 아니면 이들 중 어느 것도 없는지 알아내야 합니다.

그 일을 하거나 알려면 어떻게 해야 합니까?

감사해요

Answer 1

다음 형식의 문자열을 고려하세요. 4^a 3 4^b.우리가 찾을 수 있을까요? w, g 우리를 위해 a, b?글쎄, 우리는 그걸 알아 g 같아야 합니다 b, 그런 다음 선택할 수 있습니다. w = a + g.부터 a, b 그리고 g 자연수이므로 자연수이기도 합니다. w;대답은 그렇습니다. 다음 형식의 문자열에 대해서는 그렇습니다. 4^a 3 4^b, 귀하의 언어로 된 문자열이 있습니다.

형식의 모든 문자열의 언어 4^a 3 4^b 정규식으로 설명됩니다. 4* 3 4* 따라서 귀하의 언어는 규칙적이고, 맥락이 없으며, 결정 가능하고 인식 가능합니다.

귀하의 언어가 규칙적이지 않다고 가정해 보십시오.어떻게 알 수 있었어?Myhill-Nerode 정리 또는 정규 언어에 대한 Pumping Lemma를 사용하여 해당 언어가 정규 언어라고 가정하는 것에서 모순을 도출할 수 있습니다.

귀하의 언어가 문맥 자유가 아니라고 가정해 보십시오.문맥 없는 언어에 대한 Pumping Lemma를 사용하면 해당 언어가 문맥 없는 언어라는 가정에서 모순을 도출할 수 있습니다.

물론, 귀하의 언어가 결정 가능하지 않거나 인식 가능하지 않다면 다양한 방법으로 이를 증명할 수도 있습니다.