2.2 형식 언어와 오토마타 — 언어의 구조와 인식기의 경계
"정규식이면 이 정도는 다 처리할 수 있다"는 말은 세 가지 다른 것 — 수학적 대상인 정규 언어, POSIX·ECMAScript 같은 표면 문법으로서의 정규식, 그 문법을 실행하는 특정 엔진의 전략 — 을 뭉뚱그린다. 이 문서는 셋을 분리하고, DFA·NFA·Thompson construction으로 정규 언어의 인식 모델을 세운 뒤, pumping lemma로 그 모델이 무너지는 지점을 확인한다.
학습 목표
- 알파벳·문자열·언어의 정의로 촘스키 계층에서 정규 언어와 문맥 자유 언어의 위치를 설명한다.
- DFA와 NFA(엡실론 전이 포함)의 실행을 상태(집합) 추적으로 설명하고, subset construction이 둘의 표현력이 같음을 보이는 방식을 설명한다.
- Thompson construction으로 정규식의 연결·선택·반복 연산자를 NFA로 조립하는 과정을 재현한다.
- pumping lemma 논증으로 임의 깊이 중첩이나 개수 대응을 요구하는 언어가 정규 언어가 아님을 판별한다.
- 정규 언어, 정규식 표기, 실행 전략을 구분해 "정규식으로 이건 못 한다"는 주장을 정확한 근거로 검증하거나 반박한다.
배경: 왜 이것이 존재하는가
컴파일러가 소스 코드를 토큰으로 자르고, 방화벽이 패킷 헤더 형식을 검사하고, 입력 검증기가 이메일 형식을 확인하는 작업은 공통된 질문 하나로 환원된다 — 주어진 문자열이 어떤 언어에 속하는가? 이 질문에 답하는 두 가지 방법이 1950년대에 각각 다른 동기에서 등장해 서로 맞물렸다.
촘스키(Chomsky, 1956)는 자연어 문법을 형식화하려고 생성 규칙(production rule)의 계층을 제안했다 — 문법이 얼마나 강력한 재작성 규칙을 허용하는지에 따라 언어를 분류한 것이다. 거의 같은 시기에 클레이니(Kleene, 1956)는 McCulloch–Pitts의 신경망 모델이 인식할 수 있는 이벤트 집합("regular events")을 유한 상태 기계로 특징지었고, 라빈과 스콧(Rabin–Scott, 1959)이 비결정론적 유한 오토마타(NFA)를 정식화하며 결정론적 유한 오토마타(DFA)와 표현력이 같음을 증명했다. 결과적으로 "문법이 얼마나 제약되어 있는가"(생성기 관점)와 "어떤 기계로 인식할 수 있는가"(인식기 관점)가 같은 언어 집합을 서로 다른 방향에서 가리키는 것으로 밝혀졌다. 이 대응이 촘스키 계층이다.
이 지도가 실무에 중요한 이유는 단순하다. 입력 구조마다 필요한 계산 모델의 최소 크기가 다르고, 그 최소 크기를 안 뒤에 도구를 고르면 표현력이 부족한 도구를 억지로 쓰거나 과한 도구를 낭비하는 실수를 피할 수 있다.
핵심 개념
알파벳, 문자열, 언어 — 그리고 두 가지 정의 방법
알파벳 Σ는 기호의 유한 집합(예: {a, b})이고, 문자열은 Σ의 기호를 유한 번 나열한 것, 언어 L은 그런 문자열들의 집합(L ⊆ Σ*)이다. 같은 언어를 정의하는 방법은 두 가지다.
- 생성기(grammar): 시작 기호에서 출발해 재작성 규칙을 반복 적용하며 문자열을 만들어 내는 절차.
- 인식기(automaton): 입력 문자열을 받아 그 언어에 속하는지 판정하는 기계.
이 이중성은 2.1에서 세운 구문·의미의 분리와 같은 구조다 — 문법은 "무엇을 만들 수 있는가"(구문적 생성)를, 오토마타는 "무엇을 받아들이는가"(의미적 판정)를 각각 담당하고, 같은 언어를 서로 다른 방향에서 정의한다.
촘스키 계층 — 문법의 제약이 인식기의 계산 능력을 정한다
| Type | 문법 제약 | 인식기 | 챕터 2의 취급 |
|---|---|---|---|
| 3 (정규) | 우변에 비단말 하나만(선형) | 유한 오토마타(DFA/NFA) | 이 문서의 중심 |
| 2 (문맥 자유) | 좌변이 비단말 하나 | 푸시다운 오토마타(PDA, 스택 1개) | 표현력의 경계까지만, 파싱은 위임 |
| 1 (문맥 의존) | 우변 길이 ≥ 좌변 길이 | 선형 유계 오토마타 | 계층 지도에서 위치만 |
| 0 (제한 없음) | 임의의 재작성 규칙 | 튜링 기계 | 2.3에서 계산 모델로 재등장 |
네 계층은 포함 관계다(정규 ⊂ 문맥 자유 ⊂ 문맥 의존 ⊂ 재귀적 열거 가능). 이 챕터는 Type 3과 Type 2의 경계 — "유한한 상태만으로 충분한가, 스택이 필요한가" — 에 집중한다. 문맥 의존 문법의 세부 구현과 오토마타 최소화 알고리즘은 범위 밖이다.
DFA — 결정론이 주는 단순함
**결정론적 유한 오토마타(DFA)**는 (Q, Σ, δ, q₀, F)로 정의된다: 상태의 유한 집합 Q, 알파벳 Σ, 전이 함수 δ: Q × Σ → Q, 시작 상태 q₀, 수용 상태 집합 F. 핵심은 δ가 함수라는 것 — 상태 하나와 입력 기호 하나가 주어지면 다음 상태가 정확히 하나로 정해진다. 실행은 그래서 단순하다: 지금 상태 하나를 들고 입력을 한 글자씩 읽으며 δ를 따라가고, 끝에 F에 있으면 수용한다. 메모리는 "지금 상태가 무엇인가" 하나면 충분하다.
NFA와 엡실론 전이 — "동시에 여러 경로"의 정확한 의미
**비결정론적 유한 오토마타(NFA)**는 δ가 함수가 아니라 관계다: 상태와 기호 하나에 대해 다음 상태가 0개, 1개, 여러 개일 수 있고, 입력을 소비하지 않는 엡실론 전이(ε-transition)도 허용한다. "비결정론"이라는 말 때문에 NFA를 실행할 때 "가능한 경로마다 스레드를 하나씩 띄워 무한히 분기한다"고 상상하기 쉽지만, 이것은 정확하지 않다. 실제 실행(lockstep simulation)은 매 입력 위치에서 "지금 도달 가능한 상태들의 집합" 하나만 유지한다.
- 엡실론 전이로 입력 소비 없이 도달 가능한 모든 상태를 모으는 것을 엡실론 폐포(epsilon closure)라 부른다.
- 문자 하나를 읽으면, 현재 상태 집합의 각 상태에서 그 문자로 갈 수 있는 상태들을 모으고, 다시 엡실론 폐포를 취해 다음 상태 집합을 만든다.
- 상태 집합은 상태 ID로 중복 제거된다. 같은 상태에 여러 경로로 도달해도 집합에는 한 번만 들어간다.
상태가 n개인 NFA라면 이 집합의 크기는 최대 n을 넘지 않는다. "스레드가 무한히 늘어난다"는 통념과 달리, 실제 실행 중 유지하는 상태 공간은 원래 NFA 크기로 상한이 고정된다. 이 문서의 미니 실험이 이 상태 집합을 한 단계씩 눈으로 확인한다.
Subset construction은 이 아이디어를 오프라인으로 미리 계산해 NFA와 동등한 DFA를 만드는 알고리즘이다 — DFA의 각 상태를 "NFA 상태들의 부분집합"으로 정의하면 된다. 상태 수가 최악의 경우 2ⁿ으로 늘 수 있지만(존재한다는 것과 크기가 작다는 것은 다른 주장이다), NFA로 인식되는 언어와 DFA로 인식되는 언어의 집합이 정확히 같다는 것을 이 구성이 증명한다. 결정론(DFA)과 비결정론(NFA)이 표현력에서는 동등하고, 차이는 실행 방식과 상태 수 트레이드오프에 있을 뿐이다.
Thompson construction — 정규식을 NFA로 조립한다
Thompson construction(1968)은 정규식의 연산자마다 정해진 모양의 NFA 조각(fragment)을 만들고 이어 붙이는 알고리즘이다. 조각은 하나의 시작점과 하나의 끝점을 갖도록 통일해서, 연산자가 조각을 재귀적으로 조합하기만 하면 되게 만든다.
리터럴 a: ─▶(●)──a──▶(●)
연결 R1R2: ─▶[ R1 ]──▶[ R2 ]▶
선택 R1|R2: ┌─▶[ R1 ]─┐
─▶(●)─┤ ├─▶(●)
└─▶[ R2 ]─┘
반복 R*: ┌───────────┐
─▶(●)─┼─▶[ R ]────┘
└──────────────▶(●)각 연산자가 추가하는 상태 수는 상수(리터럴 1개, 선택·반복은 몇 개의 분기 상태)이므로, 전체 NFA의 상태 수는 정규식 길이에 선형으로 비례한다. 이 문서의 미니 실험은 (a|aa)+b를 위 규칙대로 손으로 조립한 8개 상태의 NFA를 그대로 사용한다.
Pumping lemma — 유한 상태로 셀 수 없는 것
정규 언어는 인식기가 유한한 메모리(상태 수)만 갖는다는 제약을 받는다. Pumping lemma는 이 제약이 만드는 한계를 정확히 진술한다.
L이 정규 언어이면, 어떤 길이p(pumping length)가 존재해서,L에 속하고 길이가p이상인 모든 문자열s는s = xyz로 나눌 수 있다. 이때|xy| ≤ p,|y| > 0이고, 모든i ≥ 0에 대해xyⁱz도L에 속한다.
증명의 핵심은 비둘기집 원리다 — 상태가 p개뿐인 DFA가 길이 p 이상인 문자열을 읽으면, 처음 p글자를 읽는 동안 같은 상태를 두 번 이상 방문할 수밖에 없다. 그 반복 구간이 y이고, y를 몇 번이든 반복해도(i번) 자동으로 같은 상태로 돌아오므로 수용 여부가 바뀌지 않는다.
이 lemma로 정규 언어가 아님을 보이는 표준 논증 구조는 대우(반증)다: L이 정규라고 가정하고, L에 속하면서도 pumping lemma의 결론을 위반하는 문자열 하나를 구성해 모순을 끌어낸다. 대표 사례 L = {aⁿbⁿ : n ≥ 0}(a와 b의 개수가 같아야 하는 언어)을 보자.
L이 정규라고 가정하면 pumping lengthp가 존재한다.s = aᵖbᵖ를 고른다.s ∈ L이고 길이는2p ≥ p다.|xy| ≤ p이므로xy는 전부a로만 이루어진 구간 안에 있다. 따라서y도a만으로 구성되고|y| > 0이다.xy²z를 만들면a의 개수만 늘어나고b의 개수는 그대로다.a와b의 개수가 달라졌으므로xy²z ∉ L이다.- pumping lemma는
xy²z ∈ L을 요구했으므로 모순이다. 따라서L은 정규 언어가 아니다.
이 논증이 말하는 실무적 사실은 유한 상태 기계는 "지금까지 몇 개를 봤는지"를 무한정 기억할 수 없다는 것이다. aⁿbⁿ 같은 개수 대응, 괄호나 태그의 임의 깊이 중첩은 "다음에 무엇이 와야 하는가"를 정하기 위해 원리적으로 무한한 카운터(또는 그와 동등한 무한 메모리)가 필요하고, 유한 상태로는 흉내 낼 수 없다.
CFG와 PDA — 스택이 주는 것
**문맥 자유 문법(CFG)**은 좌변이 비단말 기호 하나인 재작성 규칙만 허용한다. S → aSb | ε 같은 재귀 규칙으로 aⁿbⁿ을 정확히 생성할 수 있다. 이를 인식하는 기계가 **푸시다운 오토마타(PDA)**로, 유한 상태에 스택 하나를 더한 것이다. a를 읽을 때마다 스택에 쌓고 b를 읽을 때마다 하나씩 꺼내면, 스택이 정확히 비었을 때만 개수가 일치했다는 것을 안다 — 유한 상태로는 셀 수 없던 "지금까지 쌓인 개수"를 스택 깊이가 대신 기억해 주는 것이다. 실제 파싱 알고리즘(재귀 하강, LR 계열)이 이 PDA 모델을 어떻게 구현하는지는 챕터 5의 렉싱과 파싱에서 다룬다. 여기서 필요한 결론은 표현력의 경계선이 어디인가 뿐이다: 유한 상태로 충분한 구조(정규 언어)와 스택(또는 재귀)이 필요한 구조(문맥 자유 언어)는 다른 계산 모델을 요구한다.
실무 관점
세 가지를 뭉뚱그리지 않는다
"정규식"이라는 말은 실무에서 세 가지를 동시에 가리킨다. 이 챕터가 가장 강조하는 구분이다.
- 정규 언어(수학적 대상): 유한 오토마타로 인식 가능한 언어의 집합. Kleene의 정리가 정의한 이 클래스는 특정 문법이나 엔진과 무관하다.
- 정규식 표기(표면 문법): POSIX, ECMAScript(
RegExp) 등 각 표준이 정의하는 글로 쓰는 문법.., 문자 클래스, anchor 같은 편의 기능은 정규 언어의 표현력을 넘지 않지만, backreference(\1처럼 앞서 매칭된 부분을 다시 참조하는 것)는 명백히 정규 언어의 범위를 벗어난다 —(a+)\1이 인식하는 "같은 문자열이 반복되는가"는 유한 상태로 셀 수 없는 임의 길이 대응이 필요하기 때문이다(pumping lemma로 같은 논증이 성립한다). Lookaround(zero-width assertion,(?=...),(?<=...))는 그 안의 부분식이 정규식이라는 조건 아래서는 인식 언어의 클래스 자체를 넓히지 않는다고 알려져 있지만, 엔진이 그것을 실행하는 방식은 또 다른 문제다. - 엔진의 실행 전략: 같은 정규 언어를 실행하는 방법은 하나가 아니다. lockstep NFA 시뮬레이션(RE2, Rust
regex, Goregexp)은 상태 집합을 유지하며 입력 길이에 선형인 시간을 보장하지만 backreference처럼 정규 언어를 벗어난 확장을 구조적으로 지원하기 어렵다. 백트래킹 엔진(PCRE, Pythonre, JavaPattern, JavaScriptRegExp의 대부분 구현)은Split의 각 분기를 깊이 우선으로 시도해 backreference나 lookaround 같은 확장을 자연스럽게 지원하지만, 이 문서의 미니 실험이 보여 주듯 같은 정규 언어를 실행할 때도 최악의 경우 지수 시간이 될 수 있다.
정규 언어인지(표현력), 어떤 문법 확장을 쓰는지(표면 문법), 어느 엔진이 어떻게 실행하는지(전략)는 서로 독립적인 질문이다. "이 정규식은 정규 언어를 넘어선다"와 "이 정규식은 이 엔진에서 느리다"는 완전히 다른 주장이고, 하나가 다른 하나를 함축하지 않는다 — 정규 언어인 패턴도 백트래킹 엔진에서는 지수 시간이 될 수 있고(이 문서의 미니 실험), 정규 언어를 벗어난 backreference 패턴도 입력이 짧으면 실무에서 문제없이 빠르게 끝난다.
"정규식으로 HTML을 파싱할 수 없다"는 구호 대신
이 구호에는 진실이 있다 — 일반적인 HTML은 임의 깊이로 중첩되는 태그 구조를 갖고, pumping lemma의 논증이 그대로 적용되어 정규 언어가 아니다(균형 잡힌 태그 쌍은 aⁿbⁿ류 문제와 본질적으로 같다). 하지만 이 사실을 "정규식은 항상 쓸모없다"로 확장하는 것은 성급하다. 실무 판단은 다음 질문으로 갈린다.
- 입력이 신뢰할 수 있는 좁은 문법인가? 사용자가 임의로 작성한 HTML 전체가 아니라, 내부 시스템이 생성한 태그 하나(
<span class="...">)의 속성만 뽑는다면 그 부분 문법은 유한 깊이이고 정규식으로 충분할 수 있다. - 허용할 중첩 깊이가 유한하고 작은가? 정규식은 유한한 반복으로 유한 깊이의 중첩을 흉내 낼 수 있다(예: 깊이 3까지의 중첩을 3단계로 펼쳐 쓰기). 다만 이는 "정규식이 중첩을 인식한다"가 아니라 "특정 유한 깊이까지 하드코딩했다"는 뜻이며, 그 깊이를 넘는 입력은 정의상 처리하지 못한다.
- 엔진이 어떤 확장을 제공하는가? PCRE 같은 일부 엔진은 재귀 패턴(
(?R)) 확장을 제공해 균형 구조를 처리할 수 있게 하지만, 이는 더 이상 정규 언어의 실행이 아니라 사실상 별도의 파서를 정규식 문법 안에 넣은 것이다. - 신뢰 경계가 어디인가? 신뢰할 수 없는 입력(공격자가 통제하는 HTML)을 정규식으로 파싱하려는 시도는 표현력 문제 이전에 보안 문제다 — 2.4의 ReDoS 논의로 이어진다.
"할 수 있다/없다"가 아니라 "이 입력 문법, 이 중첩 깊이, 이 엔진 확장, 이 신뢰 경계에서 타당한가"를 묻는 것이 정확한 판단이다.
더 깊이: subset construction을 작은 예로 확인한다
NFA N이 상태 {0,1,2}, 시작 0, 수용 {2}, 전이가 0 --a--> 0, 0 --a--> 1, 1 --b--> 2라고 하자(a*ab 패턴을 어설프게 흉내 낸 예). Subset construction은 시작 상태를 {0}으로 두고, 각 부분집합에서 각 기호로 갈 수 있는 다음 부분집합을 계산해 새 DFA 상태로 추가한다.
DFA 상태 {0} --a--> {0,1} (NFA의 0에서 a로 0과 1 모두 갈 수 있다)
DFA 상태 {0,1} --a--> {0,1} (0은 계속 0,1로, 1은 a 전이 없음)
DFA 상태 {0,1} --b--> {2} (1이 b로 2로 간다 — 수용 상태 포함!)
DFA 상태 {2} --a,b--> {} (더 이상 전이 없음 — 죽은 상태)만들어진 DFA는 상태 4개({0}, {0,1}, {2}, {})로 원래 NFA와 정확히 같은 언어를 인식한다. 상태 수가 늘긴 했지만(3개 → 4개, 최악의 경우 2³=8개까지 가능했다) 결정론적으로 바뀌었다 — 각 상태에서 각 기호에 대한 다음 상태가 정확히 하나다. 이 구성이 일반적으로 항상 가능하다는 것이 NFA와 DFA의 표현력이 같다는 증명의 핵심이다.
미니 실험: (a|aa)+b에서 lockstep과 백트래킹의 방문 횟수 비교
(a|aa)+b를 Thompson construction 규칙대로 손으로 조립한 NFA(8개 상태)에 끝의 b가 없는 입력(a를 n번 반복)을 넣는다. 같은 그래프를 lockstep 상태 집합 실행기와, Split을 깊이 우선으로 탐색하되 (상태, 입력 위치)를 memoize하지 않는 백트래킹 실행기로 각각 돌려 방문 횟수를 비교한다.
// nfa-vs-backtracking.ts — node nfa-vs-backtracking.ts 로 실행
// Thompson construction이 만드는 NFA는 세 종류의 상태만으로 충분하다.
type State =
| { kind: "Char"; char: string; next: number } // 문자 하나를 소비하고 next로 이동
| { kind: "Split"; next1: number; next2: number } // 입력을 소비하지 않고 두 갈래로 분기(epsilon)
| { kind: "Match" }; // 성공 상태
// (a|aa)+b 를 손으로 구성한다.
// 상태 0: Split(1, 3) alt 진입: "a" 분기(1) 또는 "aa" 분기(3)
// 상태 1: Char('a', 2) "a" 분기의 유일한 문자
// 상태 2: Split(6, 6) "a" 분기 완료 -> 반복 결정 지점(6)으로 합류
// 상태 3: Char('a', 4) "aa" 분기 첫 글자
// 상태 4: Char('a', 5) "aa" 분기 둘째 글자
// 상태 5: Split(6, 6) "aa" 분기 완료 -> 반복 결정 지점으로 합류
// 상태 6: Split(0, 7) plus의 핵심: 다시 alt(0)로 돌아가 반복하거나, 탈출(7)한다
// 상태 7: Char('b', 8) 그룹 뒤의 리터럴 b
// 상태 8: Match
const states: State[] = [
{ kind: "Split", next1: 1, next2: 3 }, // 0
{ kind: "Char", char: "a", next: 2 }, // 1
{ kind: "Split", next1: 6, next2: 6 }, // 2
{ kind: "Char", char: "a", next: 4 }, // 3
{ kind: "Char", char: "a", next: 5 }, // 4
{ kind: "Split", next1: 6, next2: 6 }, // 5
{ kind: "Split", next1: 0, next2: 7 }, // 6
{ kind: "Char", char: "b", next: 8 }, // 7
{ kind: "Match" }, // 8
];
const START = 0;
interface LockstepResult { matched: boolean; steps: number; maxActiveStates: number; }
// epsilon-closure: 문자를 소비하지 않고 도달 가능한 모든 상태를 상태 ID로 중복 제거하며 모은다.
function addState(list: number[], seen: Set<number>, id: number) {
if (seen.has(id)) return; // 이미 방문한 상태 ID는 다시 펼치지 않는다 — lockstep의 핵심
seen.add(id);
list.push(id);
const s = states[id];
if (s.kind === "Split") { addState(list, seen, s.next1); addState(list, seen, s.next2); }
}
function lockstepRun(input: string): LockstepResult {
let current: number[] = [];
addState(current, new Set(), START);
let steps = current.length;
let maxActiveStates = current.length;
for (let pos = 0; pos < input.length; pos++) {
const ch = input[pos];
const nextSeen = new Set<number>();
const nextList: number[] = [];
for (const id of current) {
const s = states[id];
if (s.kind === "Char" && s.char === ch) addState(nextList, nextSeen, s.next);
}
current = nextList;
steps += current.length;
maxActiveStates = Math.max(maxActiveStates, current.length);
if (current.length === 0) break;
}
return { matched: current.some((id) => states[id].kind === "Match"), steps, maxActiveStates };
}
interface BacktrackResult {
matched: boolean; steps: number; branches: number; maxStackDepth: number; aborted: boolean;
}
// naive backtracking: 같은 그래프를 깊이 우선으로 탐색하되 (state, position)을 memoize하지 않는다.
function backtrackRun(input: string, maxSteps: number): BacktrackResult {
let steps = 0, branches = 0, maxDepth = 0, aborted = false;
function go(id: number, pos: number, depth: number): boolean {
if (aborted) return false;
steps++;
maxDepth = Math.max(maxDepth, depth);
if (steps > maxSteps) { aborted = true; return false; }
const s = states[id];
if (s.kind === "Match") return pos === input.length;
if (s.kind === "Char") {
return pos < input.length && input[pos] === s.char && go(s.next, pos + 1, depth + 1);
}
branches++; // Split: 첫 분기를 끝까지 시도하고, 실패해야만 둘째 분기를 시도한다
if (go(s.next1, pos, depth + 1)) return true;
if (aborted) return false;
return go(s.next2, pos, depth + 1);
}
const matched = go(START, 0, 0);
return { matched: aborted ? false : matched, steps, branches, maxStackDepth: maxDepth, aborted };
}
console.log("n\tlockstep.steps\tbacktrack.steps\tbacktrack.branches\tbacktrack.aborted");
const MAX_STEPS = 2_000_000;
for (let n = 1; n <= 24; n++) {
const input = "a".repeat(n); // 끝에 b가 없으므로 항상 실패한다
const ls = lockstepRun(input);
const bt = backtrackRun(input, MAX_STEPS);
console.log(`${n}\t${ls.steps}\t${bt.steps}\t${bt.branches}\t${bt.aborted}`);
}Node.js v24.14.0, Apple M5 Pro, macOS 26.6.2에서 실행한 결과(일부 발췌)다.
n lockstep.steps backtrack.steps backtrack.branches backtrack.aborted
1 10 15 6 false
4 34 402 171 false
8 66 22646 9651 false
10 82 169062 72051 false
12 98 1261926 537811 false
13 106 2000001 852374 true <- 백트래킹은 budget 초과로 중단
20 162 2000001 852382 true
24 194 2000001 852388 truelockstep의 steps는 n에 거의 정확히 선형으로 늘어난다(입력 하나당 상태 집합 크기가 최대 8로 고정되어 있으므로 당연하다). 백트래킹의 steps는 n=1의 15에서 n=12의 126만까지, 대략 매 단계 2.7배씩 불어나며 n=13부터는 200만 스텝의 budget을 넘겨 중단된다. 같은 NFA 그래프, 같은 입력을 두고 실행 순서와 중복 제거 여부만 다른데도 이 정도 차이가 난다. 원인은 (a|aa)+가 만드는 모호성이다 — a를 n개 쌓는 방법은 "1개씩" 분할과 "2개씩" 분할을 어떻게 섞느냐에 따라 조합적으로 많고, 끝에 b가 없어 모든 분할이 결국 실패하므로 백트래킹은 그 많은 분할을 전부 시도해야 실패를 확정한다. 반면 lockstep은 그 모든 분할이 도달하는 상태들을 애초에 하나의 집합으로 겹쳐 두므로 분할의 가짓수와 무관하게 상태 집합 크기만큼만 일한다.
같은 실행기로 반복이 없거나(a+b, 모호한 선택 없이 순수 반복만 있음) 모호성이 없는((a|aa)b, 반복이 없어 분할이 한 번뿐) 패턴을 n=24 입력에 돌리면 각각 steps=73, steps=6으로 폭발하지 않는다. 모호한 선택(alternation)과 반복(repetition)이 함께 있어야 분할의 가짓수가 조합적으로 늘어나고, 끝에 도달하지 못하는 실패(late failure)가 그 모든 가짓수를 강제로 다 시도하게 만든다 — 셋 중 하나라도 빠지면 폭발하지 않는다. 반대로 이 결과를 "NFA 실행은 항상 lockstep이 이긴다"로 일반화해서는 안 된다. lockstep이 입력 길이당 상수 시간을 보장하는 대가는 상태 집합 관리이고, 백트래킹은 그 관리 없이 실행되므로 모호성이 적은 실전 패턴에서는 오히려 더 적은 오버헤드로 동작할 수 있다.
정리
- 언어는 생성기(문법)와 인식기(오토마타)라는 두 관점으로 정의할 수 있고, 촘스키 계층은 문법의 제약과 인식기의 계산 능력을 대응시킨다.
- DFA는 결정론적 전이로 상태 하나만 추적하면 되고, NFA는 상태 집합(엡실론 폐포 포함)을 추적한다. Subset construction은 둘의 표현력이 같음을 구성적으로 증명한다.
- Thompson construction은 정규식의 각 연산자를 상수 크기의 NFA 조각으로 만들어 이어 붙이므로 전체 NFA 크기는 정규식 길이에 선형이다.
- pumping lemma는 유한 상태 기계가 임의 길이의 개수 대응이나 중첩 깊이를 셀 수 없다는 것을 비둘기집 원리로 증명하고, 이 논증으로 특정 언어가 정규 언어가 아님을 보일 수 있다.
- 정규 언어(수학적 대상), 정규식 표기(표면 문법), 엔진의 실행 전략(lockstep 대 백트래킹)은 서로 다른 층이며, 하나에 대한 판단이 다른 것을 함축하지 않는다.
- 모호한 선택과 반복이 결합하고 실패가 늦게 확정될 때 백트래킹은 지수적으로 방문 횟수가 늘어나지만, lockstep은 상태 집합 중복 제거로 입력 길이에 선형으로 유지된다.
확인 문제
1. 동료가 "이 정규식 엔진은 backreference를 지원하니 lockstep NFA 시뮬레이션을 쓰고 있을 리 없다"고 말했다. 이 추론이 왜 타당한지, 그리고 "이 엔진이 lockstep을 쓰지 않으니 정규 언어보다 강력한 것을 전부 표현할 수 있다"는 역방향 주장은 왜 성립하지 않는지 설명하라.
정답과 해설
Backreference는 이전에 매칭된 부분 문자열을 다시 참조해야 하므로 "지금까지 무엇이 매칭됐는가"를 무한정 기억해야 할 수 있다 — 이는 pumping lemma의 논증이 적용되는 정규 언어의 범위를 벗어난다. Lockstep NFA 시뮬레이션은 유한한 상태 ID 집합만 유지하므로 이런 무한 기억을 표현할 수 없고, 따라서 backreference를 지원하는 엔진은 구조적으로 백트래킹(또는 이에 준하는 별도 메커니즘)을 써야 한다는 추론은 타당하다. 그러나 역방향은 성립하지 않는다 — 엔진이 백트래킹을 쓴다는 사실 자체가 "정규 언어보다 강력한 모든 것을 표현할 수 있다"는 뜻은 아니다. 백트래킹은 실행 전략일 뿐이고, 그 엔진이 실제로 backreference나 다른 확장 문법을 지원하도록 구현했는지는 별개의 설계 선택이다. 표현력(문법이 무엇을 인정하는가)과 실행 전략(그것을 어떻게 실행하는가)을 섞으면 안 된다.
2. 어떤 로그 형식이 "key1=value1;key2=value2;...;keyN=valueN"처럼 세미콜론으로 구분된 key=value 쌍을 임의 개수만큼 나열하되, 각 줄의 쌍의 개수가 그 줄 맨 앞의 숫자와 정확히 일치해야 유효하다는 규칙을 추가하면("3;key1=value1;key2=value2;key3=value3"), 이 언어가 정규 언어인지 판별하고 근거를 pumping lemma 논증으로 제시하라.
정답과 해설
정규 언어가 아니다. 앞의 숫자 n과 실제 key=value 쌍의 개수가 일치해야 한다는 조건은 aⁿbⁿ류의 개수 대응이다. L이 정규라고 가정하고 pumping length p보다 큰 n에 대해 s = "n;key1=v1;...;keyN=vN"을 고르면, |xy| ≤ p 조건 때문에 y는 문자열 앞부분(숫자를 표현하는 자릿수 또는 그 근처)에 들어가고, y를 반복하면 앞의 숫자 표현은 바뀌는데 뒤에 나열된 key=value 쌍의 개수는 바뀌지 않는다(혹은 그 반대). 어느 경우든 "숫자와 쌍의 개수가 일치한다"는 조건이 깨지므로 xy²z ∉ L이 되어 모순이다. 유한 상태로는 "지금까지 세미콜론을 몇 번 봤는가"를 임의 크기로 셀 수 없기 때문이며, 이 형식을 검증하려면 정규식이 아니라 파서(또는 두 값을 각각 캡처해 수치 비교하는 후처리)가 필요하다.
3. 내부 CI 도구가 생성하는 XML은 항상 깊이 2까지만 중첩된다는 것이 보장되어 있다(스키마로 고정됨). 팀원이 "XML은 문맥 자유 언어이니 정규식으로 파싱하면 안 된다"며 무조건 전용 XML 파서 도입을 주장한다. 이 문서의 실무 판단 기준으로 이 주장을 평가하라.
정답과 해설
"XML은 일반적으로 문맥 자유 언어(임의 깊이 중첩)이므로 정규식으로 표현할 수 없다"는 명제 자체는 맞다. 하지만 이 사례는 일반적인 XML이 아니라 깊이 2로 고정된, 신뢰할 수 있는 내부 생성기의 출력이라는 좁은 문법이다. 유한 깊이가 스키마로 보장된다면 그 깊이만큼 정규식을 유한 번 펼쳐 쓰는 것으로 충분히 표현할 수 있고, 이는 "정규식이 재귀를 인식한다"는 뜻이 아니라 "유한한 특정 깊이를 하드코딩했다"는 뜻이다. 무조건 전용 파서를 강제하기보다, 입력이 실제로 신뢰할 수 있고 깊이가 고정되어 있는지 확인한 뒤 정규식으로 충분한지, 스키마가 바뀔 가능성이 있어 파서가 더 안전한지를 판단해야 한다. 단, 신뢰할 수 없는 외부 입력이라면 깊이 보장 자체를 믿을 수 없으므로 이 판단은 뒤집힌다.
참고 자료
- Noam Chomsky, "Three Models for the Description of Language" (IRE Transactions on Information Theory, 1956) — 촘스키 계층을 처음 제시한 원 논문.
- Stephen Kleene, "Representation of Events in Nerve Nets and Finite Automata" (1956) — 정규 이벤트와 유한 오토마타의 대응을 다룬 원 논문.
- Michael Rabin, Dana Scott, "Finite Automata and Their Decision Problems" (IBM Journal of Research and Development, 1959) — NFA를 정식화하고 DFA와의 표현력 동등성을 증명한 원 논문.
- Ken Thompson, "Regular Expression Search Algorithm" (Communications of the ACM, 1968) — 정규식을 NFA로 변환해 검색하는 construction의 원 논문.
- Ecma International, ECMA-262,
RegExp(Regular Expression) Objects — ECMAScript 정규식 문법의 공식 명세. 정규식 문법과 실행 알고리즘은 이 명세가 규정하지 않는다는 점을 확인할 수 있다. - The Open Group, The Open Group Base Specifications, Regular Expressions — POSIX 기본 정규식(BRE)과 확장 정규식(ERE)의 공식 정의.
- Russ Cox, Regular Expression Matching Can Be Simple And Fast (2007) — lockstep NFA 시뮬레이션과 백트래킹의 실행 비용 차이를 실측과 함께 해부한 글. 1.3에서도 인용한 자료다.