보조 정리 보조 펌프

Question

최근에는 언어가 규칙적이지 않은 것을 보여주기 위해 펌프 보조 정리를 사용하도록 요청 받았으며, 불행히도 잘못된 대답을 얻었습니다. 다음

증명하는 언어는 비정규이다 L = {A ^I B ^J C ^K I = J 또는 J = K}

펌핑의 정의 다음과 같이 내가 주어진 보조 정리는 다음과 같습니다

1. 상대는 m
내가 펌핑 보조 정리 모순 w를 선택 할
2. 을 선택합니다. m을 사용하여 문자열 w ∈ L을 선택하십시오. 여기서 | w | ≥ m
3. 상대방은 제약 조건에 따라 w의 분해를 선택합니다. 발견하는 경우 _내가 ∉ L. w 펌핑 문자열, L은 정규되지 않도록이 주체가 나를 이해하기 매우 어려운 것으로 입증되었습니다

는 나는 내가를 선택하려고 나는 것 같은 느낌 그것으로 인해 완전한 공수가 생기므로, 어떻게 펌핑 보조 정리를 적절하게 적용 할 것인지에 대한 자세한 설명을 이해할 수있을 것입니다.

Answer 1

직관적으로, 펌핑 보조 정리에 따르면 정규 언어 L에서 충분한 길이의 단어 (길이는 언어 L에만 의존 함)는 원하는만큼 반복 될 수있는 섹션 (길이> 0)을 포함해야합니다. 이 부분을 반복하면 (원래 단어를 '펌핑') 어떤 언어로도 긴 단어가 나타납니다.

위의 정의에서 단어의 최소 길이는 m입니다. 섹션이 반복되는 횟수는 위의 정의의 네 번째 단계에서 i입니다.

일반적으로 펌핑 보조 정리는 언어 L이 규칙적이지 않다는 것을 나타내는 데 사용됩니다. 그것은 모순에 의한 증거입니다. L이 규칙적이어서 정규 언어에 대한 펌핑 보조 정리가 L에 해당한다고 가정합니다. 그런 다음 L이 충분한 길이 * 인 단어 w를 선택하고 분해 방법에 관계없이 * 일부 펌핑 됨 단어가 언어에 없습니다. 이것은 펌핑 보조 정리와 모순됩니다 - 우리가 알고있는 것은 사실입니다. 따라서 언어가 규칙적이라는 우리의 가정이 잘못되어 언어가 규칙적이지 않습니다. *로 표시된 부분은 일을 쉽게하기 위해 선택할 수 없습니다. 그래서 1 단계와 3 단계에서 '상대방'이 그들을 선택합니다.

단어 w는 w = x y z로 재 작성되며, 여기서 | y | > 0 및 | x y | < = m. x와 z는 길이가 0 일 수 있습니다.

일반적으로 xy를 동일한 문자로 구성된 문자열로 선택하면 (펌핑 후) 동일한 문자가 더 많으면 L이 아닌 단어가 표시됩니다

게시물의 언어 L의 i 또는 k에 대한 제한이 없으므로 i = 0이 허용된다고 가정하면 적합한 단어는 b^mc^m 일 수 있습니다 (즉, m bs 다음에 m cs). 이제 상대방이 어떤 분해를 선택하든간에 y는 항상 일부 bs로 구성됩니다. 이러한 bs를 반복하면 cs 및 no보다 bs가 많은 단어가 생기므로 i! = j 및 j! = k이며 단어가 언어에 없습니다.