1. 정규 언어와 2. 컨텍스트 – 자유 언어에 대해 정의된 두 가지 펌핑 기본 정리가 있습니다. 정규 언어에 대한 보조 정리 펌핑 모든 정규 언어 L에는 정수 n이 존재합니다. 즉, 모든 x에 대해 ? L과 |x| ? n, u, v, w가 존재하나요? ?^*, x = uvw 및 (1) |uv| ? n (2) |v| ? 1 (3) 나 모두에 대해 ? 0: 자외선^나여? L 간단히 말해서 문자열 v가 '펌프'되면, 즉 v가 여러 번 삽입되면 결과 문자열이 여전히 L에 남아 있음을 의미합니다. 펌핑 보조 정리는 언어의 불규칙성을 증명하는 데 사용됩니다. 따라서 언어가 규칙적이면 항상 펌핑 보조정리를 충족합니다. L에 없는 펌핑으로 만들어진 문자열이 하나 이상 존재하는 경우 L은 확실히 규칙적이지 않습니다. 이것의 반대가 항상 사실이 아닐 수도 있습니다. 즉, Pumping Lemma가 성립한다고 해서 해당 언어가 규칙적이라는 의미는 아닙니다.

예를 들어 L을 증명해보자.₀₁=엔? 0은 불규칙합니다. L이 규칙적이라고 가정하면 Lemma를 펌핑하여 위에 주어진 규칙을 따릅니다. 이제 x를 볼까요? L 및 |x| ? N. 따라서 Pumping Lemma에 따르면 (1) – (3)이 성립하는 u, v, w가 존재합니다. 우리는 모든 u에 대해 v, w, (1) – (3)이 성립하지 않음을 보여줍니다. (1)과 (2)가 성립하면 x = 0^N1^N= uvw |uv| ? n과 |v| ? 1. 따라서 u = 0^ㅏ, v = 0^비, w = 0^씨1^N여기서 : a + b ? 엔, 비? 1,c? 0, a + b + c = n 그러나 (3)은 i = 0 uv에서는 실패합니다.⁰w = uw = 0^ㅏ0^씨1^N= 0^{에이 + 씨}1^N? L, 이후 a + c ? N.

문맥 없는 언어(CFL)를 위한 보조 정리 펌핑 CFL에 대한 펌핑 Lemma는 모든 Context Free Language L에 대해 여러 번 '펌핑'할 수 있고 여전히 동일한 언어에 있는 두 개의 하위 문자열을 찾을 수 있음을 나타냅니다. 모든 언어 L에 대해 문자열을 다섯 부분으로 나누고 두 번째와 네 번째 하위 문자열을 펌핑합니다. 여기에서도 Pumping Lemma는 언어가 CFL이 아님을 증명하는 도구로 사용됩니다. 왜냐하면 하나의 문자열이 조건을 충족하지 않으면 해당 언어는 CFL이 아니기 때문입니다. 따라서 L이 CFL이면 모든 x에 대해 정수 n이 존재합니다. L과 |x| ? n, u, v, w, x, y가 존재하나요? ?^*, x = uvwxy 및 (1) |vwx| ? n (2) |vx| ? 1 (3) 나 모두에 대해 ? 0: 자외선^나wx^나그리고 ? 엘

위의 예에서는 0^N1^NCFL입니다. 모든 문자열은 두 위치(하나는 0이고 다른 하나는 1)에서 펌핑된 결과일 수 있기 때문입니다. L을 증명해 보겠습니다.₀₁₂=엔? 0은 컨텍스트 프리가 아닙니다. L이 Context-free라고 가정하고, Pumping Lemma에 의해 위에 주어진 규칙을 따릅니다. 이제 x를 볼까요? L 및 |x| ? N. 따라서 Pumping Lemma에 따르면 (1) – (3)이 성립하는 u, v, w, x, y가 존재합니다. 우리는 모든 u, v, w, x, y에 대해 (1) – (3)이 유지되지 않음을 보여줍니다. (1)과 (2)가 성립하면 x = 0^N1^N2^N= uvwxy |vwx| ? n과 |vx| ? 1. (1)은 vwx에 0과 2가 모두 포함되어 있지 않음을 알려줍니다. 따라서 vwx에는 0이 없거나 vwx에는 2가 없습니다. 따라서 우리가 고려해야 할 두 가지 경우가 있습니다. vwx에 0이 없다고 가정합니다. (2)에 따르면 vx는 1 또는 2를 포함합니다. 따라서 uwy는 'n'개의 0을 가지며 uwy는 'n'1보다 작거나 'n'2보다 작습니다. 그러나 (3)은 uwy = uv임을 알려줍니다.⁰wx⁰응? L. 따라서 uwy에는 동일한 수의 0이 있고 1과 2가 있으면 모순이 됩니다. vwx에 2가 없는 경우도 비슷하며 모순도 발생합니다. 따라서 L은 context-free가 아닙니다. 출처 : John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman(2003). 오토마타 이론, 언어 및 계산 소개.

이 글은 님이 기고하셨습니다. 니루팜 싱 .