일반 세트의 파워셋도 일반 세트인가요?

Question

그렇다면 그에 대한 증거는 어디서 찾을 수 있나요?그렇지 않다면 반례가 있습니까?

정규 언어의 파워셋이란 정규 언어의 모든 하위 집합 집합을 의미합니다.

고마워요, 마커스.

Answer 1

아니요.컴퓨터 과학에서는 언어 일반적으로 다음의 하위 집합으로 정의됩니다. $\{0,1\}^*$.만약에 $L$ 언어이고 그 다음은 파워셋입니다. $2^L$ 의 하위 집합이 아닙니다. $\{0,1\}^*$, 따라서 언어가 아닙니다.

(예를 들어, https://en.wikipedia.org/wiki/Formal_언어#정의.)

만약에 $L$ 유한하고 파워셋은 $2^L$ 유한하므로 Emil Jeřábek이 지적했듯이, 모든 유한 언어가 규칙적이므로 인코딩이 일반 언어가 되도록 인코딩할 수 있는 방법이 있습니다.

만약에 $L$ 그렇다면 무한하다 Yuval Filmus가 지적했듯이, 파워셋 $2^L$ 셀 수 없으므로 언어로 인코딩할 방법이 없습니다.따라서 언제 $L$ 무한한 정규 언어라면 귀하의 질문에 대한 대답은 "아니오, 합리적인 인코딩을 선택할 수 있더라도 그렇지 않습니다"입니다.