펌핑 보조정리

2026.09.02 18:16

펌핑 보조정리는 어떤 언어가 정규언어가 아님을 보이는 도구다. 유한한 상태로는 무한한 구별을 할 수 없다는 사실을, 문자열을 늘려 보는 절차로 바꿔 놓은 것이다.

DFA(Deterministic Finite Automaton, 결정적 유한 오토마타)의 상태는 말 그대로 유한하다. 그러므로 충분히 긴 문자열을 읽는 동안에는 같은 상태를 두 번 지날 수밖에 없다. 상태가 p개면 p개보다 긴 문자열을 읽는 사이에 반드시 하나가 반복된다.

q₀ ──x──▶ q ──y──▶ q ──z──▶ (종료상태)
           └────────┘
           같은 상태로 돌아온다

y가 상태를 제자리로 되돌리므로, 기계는 y를 몇 번 돌았는지 알지 못한다. xz, xyz, xyyz가 전부 같은 자리에서 끝난다. 하나를 받아들이면 나머지도 전부 받아들인다.

기계가 하나 있으면 이런 y가 반드시 생긴다는 것이 정리의 내용이다.

펌핑 보조 정리

펌핑 보조 정리의 정확한 서술은 다음과 같다.

L이 정규언어라면, 어떤 p ≥ 1이 있어서 길이가 p 이상인 모든 w ∈ L을 w = xyz로 나눌 수 있다.

|y| ≥ 1: 늘릴 부분이 비어 있지 않다
|xy| ≤ p: 앞쪽 p글자 안에서 잡힌다
xyⁱz ∈ L: 모든 i ≥ 0에 대해

i = 0이면 y를 지운 것이고, i = 2면 한 번 더 반복한 것이다. p는 대개 DFA의 상태 수다.

활용 사례

펌핑 보조 정리는 부정해서 쓰는 경우가 더 많다. L을 인식하는 DFA가 있다고 치고 모순을 끌어내는 방식이라, 내가 모르는 것과 내가 정할 수 있는 것이 번갈아 나온다.

p          모른다.  유한하다는 것만 안다
w          정한다.  L 안에서 가장 유리한 것을 고른다
x, y, z    모른다.  겹치는 자리는 기계 안의 사정이다
i          정한다.  깨지는 값 하나면 된다

상대가 L을 인식하는 DFA를 만들었다고 할 때 확실한 것은 상태가 유한하다는 것뿐이고, 개수는 그쪽 사정이다. p가 7이든 100만이든 통하는 논증이어야 한다. 겹치는 자리도 마찬가지다. w가 p보다 기니 읽는 도중 같은 상태를 두 번 지나는 것은 확실하지만, 그게 몇 번째 글자에서인지는 기계를 열어 봐야 안다. 분할이 어떻게 잡히든 통해야 한다.

반대로 w와 i는 내 몫이다. 정리가 길이 p 이상인 모든 문자열에 대해 성립한다고 했으니 L 안에서 아무거나 골라도 되고, y를 몇 바퀴 돌릴지도 깨지는 값 하나만 찾으면 된다.

L = {aⁿbⁿ | n ≥ 1}으로 해 보면 이렇게 된다. w = aᵖbᵖ을 잡으면 |xy| ≤ p이므로 겹침이 앞쪽 a 구간 안에서 일어날 수밖에 없고, y는 a만 k개(k ≥ 1) 들고 있다. 여기에 i = 2를 넣는다.

aᵖ⁺ᵏbᵖ     a만 늘고 b는 그대로다

L에 없는 문자열을 받아들이므로 그런 기계는 없다. w를 잘 잡는 것이 전부다. abab…처럼 잡았다면 겹치는 구간에 a와 b가 같이 들어가 늘려도 균형이 유지될 수 있는데, aᵖbᵖ은 상대에게 그 선택지를 주지 않는다.

같은 이야기를 기호로 줄이면 ∀가 모르는 자리, ∃가 정하는 자리다.

L이 정규      ∃p  ∀w  ∃(x,y,z)  ∀i.  xyⁱz ∈ L
정규가 아님   ∀p  ∃w  ∀(x,y,z)  ∃i.  xyⁱz ∉ L

여기서 주의할 점은, 역은 성립하지 않는다는 것이다. 펌핑 보조정리는 필요조건이다. 조건을 만족한다고 정규언어인 것은 아니므로, 정규언어임을 보이는 데는 쓸 수 없다.

L = { aⁱbʲcᵏ | i, j, k ≥ 0,  단 i = 1이면 j = k }

i ≠ 1인 문자열은 조건이 걸리지 않아 얼마든지 펌핑되고, i = 1인 문자열은 앞쪽 a 하나를 늘려 i ≥ 2로 만들어 버리면 그만이다. 그래서 펌핑은 통과하지만 정규언어는 아니다. 정규언어임을 보이려면 오토마타나 정규표현을 직접 만들거나, Myhill–Nerode 정리를 쓴다.

푸시다운 오토마타

푸시다운 오토마타에도 같은 논증이 있다. 반복되는 것이 상태가 아니라 유도 트리의 논터미널이다. 트리가 깊어지면 한 경로에 같은 논터미널이 두 번 나오고, 그 사이 구간을 통째로 반복할 수 있다.

w = uvxyz
|vy| ≥ 1
|vxy| ≤ p
uvⁱxyⁱz ∈ L

늘어나는 자리가 v와 y 두 곳이다. 양쪽이 같이 늘어나므로 aⁿbⁿ은 여기서 걸리지 않는다. 개수가 맞은 채로 늘어난다.

aⁿbⁿcⁿ은 걸린다. |vxy| ≤ p이므로 vxy는 a·b·c 세 구간 중 많아야 두 구간에 걸친다. 남은 한 구간은 손대지 못하니, 펌핑하면 개수가 어긋난다. aⁿbⁿcⁿ이 context-free가 아니라는 증명이 이것이다.

이래서 정규표현으로 HTML을 파싱하면 안된다… 여는 태그와 닫는 태그를 맞추는 일은 aⁿbⁿ이고, 중첩에 상한이 없으면 유한 상태로 안 된다. 괄호 짝 맞추기, 블록 중첩, if 중첩이 전부 같은 문제다. 렉서와 파서가 나뉘는 경계가 그래서 생긴다.

다만 이 논증은 이론상의 정규표현에 대한 것이다. PCRE 계열의 역참조나 재귀 패턴은 정규언어를 벗어나므로, (?R) 같은 것으로 괄호 짝을 맞추는 일 자체는 된다. 그때는 정규표현이라는 이름만 남고 유한 오토마타로 실행되지도 않는다.

참고

컴파일러 코드 최적화 컴파일러 클로저와 셀 컴파일러 트리 순회와 바이트코드 언어 CustomAnnotation 언어 JIT 언어 tracing JIT