주문이없는 언어에 대한 보조 정리 펌프

Question

필자는 본 교과서에서 결승전을 위해 몇 가지 문제를 겪어 왔지만 나는 그 사실을 알 수없는 한 가지 질문에 부딪쳤다. 기본적으로는 다음과 같았습니다

L = {w | w에는 1보다 많은 0이 포함되어 있습니다.

일반 언어에 대한 펌핑 보조 정리가 도움이된다는 힌트로 말합니다.

펌핑을 통해 패턴을 분해 할 수 있기 때문에 0의 첫 번째 또는 1의 문장과 같은 일부 패턴이있는 경우 언어가 비정규 인 것을 쉽게 증명할 수 있지만 여기서 유일한 요구 사항은 포함 할 수있는 단어입니다 0과 1은 순서에 관계없이 0을 더가집니다.

저는 몇 가지 경우를 생각하려고했습니다. 분명히 y = 0 인 경우, 0보다 1이 많을 때까지 y를 펌프질 할 수있었습니다. 그러나 펌핑 보조 정리가 거짓으로 판명 될 수있는 모든 가능한 경우를 고려해야하며 y가 xy | < p (여기서 p는 펌핑 길이 임). y는 0과 1 또는 1만을 포함 할 수 있습니다. 내가 여기서 뭔가 분명한 것을 놓치고 있니? 미리 감사드립니다.

Answer 1

그렇게 같은 단어를 선택할 수 숫자 N 주어진
단어는 Z = 0^L.에
Z = UVW되고 (2N)^1 N, | UV | < = n이므로 uv는 0 만 포함합니다.
따라서 v는 0 만 포함하고 | v |> = 1도 포함합니다.
L이 규칙 적이라고 가정하면, u 축은 0 L이 L.
에 있지만 v = 0^k (k> = 1)이기 때문에 uv^0w = 0^(2n-k) 1^n, 이는 k> 0이기 때문에 L에 있지 않습니다.