내가 펌핑 보조 정리에 비교적 새로운 오전

Question

펌핑 보조 정리를 이해하고, 나는이 작동하는 경우 사람이 말해 줄 수, 내가 정답을 생각 여기에 문제가 있고 그렇지 않으면 왜 안

문제 : {WWW | w는 {A, B} *}

내 접근법 :

L = WWW 유 *

(V^(K)) * L

WWW

의 서브 세트이어야 승

| | |

UVW

UVW = WWW

(U) (V^2) (w) = WWWW

WWWW는 언어 WWW 부분 때문에 정기적하지 아니다

편집 : 음, 내 이해에 따르면 우리가보고있는 "테스트 스트링"을 가져 와서 같은 부분을 반복해서 반복하는 부분과 마지막으로 다른 부분을 뒤섞는 부분으로 펌핑 보조 정리 남아있다. 내 "접근법"에서는 테스트 문자열 "www"를 가져 와서 각각 u, v 및 w로 나눕니다. 각각 v는 반복 가능 섹션이고 나머지 두 개는 동일하게 유지됩니다. 나는 v 섹션을 두 배로 늘리고 그것이 언어 www의 일부가 아닌 것처럼 보이는 wwww로 번역되는 결과 uvvw로 끝납니다. 나는 빈 문자열을 포함한다고 생각하는 조건 "w is {a, b} *"로 인해 틀렸다고 생각하며, 빈 문자열은 wwww와 www에서 실행 가능하므로 내 펌핑 보조 정리가 잘못되었습니다. 이 문제를 해결하기 위해 취해야 할 접근법을 알고 싶습니다. 그냥 연습 문제 일뿐입니다.

Answer 1

wwww가 웹 사이트에 없다는 것을 확신 할 방법이 없기 때문에 답변이 제대로 작동하지 않는다고 생각합니다. 언어.

예를 들어 let | w | 그래서 당신의 시킴으로 빨리 문자열 길이 다중 3 (일부 k에 대한 즉 3 * K) 수 : | 3K | + | 3K | + | 3K | = 9 * 3K

그래서 당신은 다른 문자열 길이 3K를 추가합니다. 당신이 1 초에 둘러싸인 P는 0을 가지고 w = 100 ... 001, 보자 길이는 또한 같은 시도 3.

의 배수 인 지금은 12K입니다. 그렇다면 아무리 펌프를 치르더라도 10..0110.0110..01 u v w이면 언어가 어긋납니다.