`{a^n b^m | n = k in k for N}`이 비정규 다

Question

L={a^n b^m | n=km for k in N}은 펌프 보조 정리를 사용하는 정규 언어가 아닌 것을 어떻게 증명해야합니까?

나는 N 일부 k에 대한 n=km으로, L에 w=a^n b^m을 단어 w을 복용하기 시작했다. 세 가지 분해는 w에 대한 있습니다

1. a^i * a^j * a^(n-i-j) b^m
2. a^i * a^(n-i) b^j * b^(m-j)
3. a^n b^i * b^j * b^(m-i-j)

점 2의 중간 부분을 펌프가) 명확하지 않은 혼합 단어가 발생합니다 L에 있지만 왜 1) 당신에게 좋은 분해를 줄 수 없는지 알아낼 수 없습니다 :

a^jx 번 펌프를 치자. 그러면 새 단어에있는 a의 양은 i+xj+n-i-j = n+(x-1)j이됩니다. m에 대해서는 n=km을 알고 있습니다. 새로운 단어가 L에 없도록 x이 있음을 보여 주어야합니다. 하지만 j=m이라고 가정 해 봅시다. n=km은 항상 k=0이 아닌 경우를 제외하고는 항상 충분한 양이 있습니다. 그렇지만 사소한 경우가 발생합니다. 그 다음 은 모두 x에 대해 {a^n b^m | n=km for k in N}의 형식입니다. 따라서 각 w에 대해 우리는 uvz의 분해를 가지고 u v^i z이 모두 i 인 경우 L에 해당합니다. 따라서, 펌핑 보조 정리에 의해, L은 규칙적이다.

무엇이 누락 되었습니까?

편집 : 주어진 펌핑 보조 정리의 제형 :

하자 L는 k 상태와 DFA 인정 정규 언어합니다. w은 길이가 >= k 인 L의 모든 단어가되도록하십시오. 그런 다음 w이 먼저 언어를 수정하는 것입니다 증거에 대한 모든 i>=0

Answer 1

아마 쉬운 방법을 L에 |uv| <=k, v>0 및 u v^i z으로 u v z과 같이 쓸 수있다.

일반 언어는 이므로은 다른 정규 표현식과 교차하여 보완됩니다.

입니다 그 반대, L' 정규 언어 인 경우 때문에 증거 L가 complement(L)을 증명하여 일반 언어, 정규 언어가 아닙니다되지 수 L을 의미한다. 교차로에서도 마찬가지입니다.

이 L ' 일반뿐만 아니라 아니라는 것을 증명하기에 충분하다 : 따라서

L' = intersection(complement(L),a*b*}) 

L'={a^nb^m|n != k*m, for any k in N} 

당신이 사용하는 어떤 부분에 대한 표시 할 수 있기 때문에 그런 증거 방법 쉬워진다 펌핑 보조 정리로 길이가 l이면 충분한 시간 동안 펌핑하여 배수에 도달 할 수 있습니다.