불규칙 함을 증명하는 것

Question

내가 언어 L = {wxwR}인데, wR은 w의 역이며, x는 최소 길이가 1이고, w는 0 또는 1로 구성 될 수 있지만 x는 1로만 구성 될 수 있습니다.

이 언어가 규칙적이지 않다는 것을 어떻게 증명합니까? 펌핑 보조 정리를 사용하는 것 외에 다른 방법이 있습니까? 펌핑 보조 정리를 사용하는 경우 x, y 및 z를 선택해야합니다. s = xyz 문자열을 선택해야합니다. 힌트를 주시면 감사하겠습니다.

감사합니다!

Answer 1

펌핑 보조 정리를 사용하는 방법에 대해 다시 살펴보아야합니다. s 문자열을 선택해야 각 파티션 x, y, z에 대해 펌핑 보조 정리 조건 중 하나가 위반됩니다.

따라서 n을 "펌핑 보조 정리 번호"라고합시다. 선택 s= 0^n 1 0^n. 1)부터 알고 계신 분은 |xy| <= n입니다. 2)에서 당신은 |y|>=1을 알고 있습니다. 따라서 y에만 0s이 포함됩니다.

3) uv^2w도 L이어야하지만, 0s의 첫 번째 블록은 두 번째 블록보다 길다. 이것은 3)을 위반 했으므로 L이 규칙적이지 않음을 의미합니다.