정규 표현식과 유한 오토마타로 이해하는 패턴 매칭

패턴 표기와 상태 기계는 같은 언어를 가리킨다

정규 표현식(Regular Expression)은 문자열 패턴을 짧은 표기로 적는 방법이고, 유한 오토마타(Finite Automaton)는 그 패턴을 상태 전이로 판별하는 모델이다. 둘은 정규 언어를 표현한다는 점에서 동등하며 서로 변환할 수 있다.

이 대응 관계 덕분에 정규 표현식의 간결함과 상태 기계의 실행 특성을 함께 활용할 수 있다. 컴파일러의 어휘 분석, 텍스트 검색과 치환, 웹 입력 검증, 네트워크 보안의 시그니처 매칭이 대표적인 활용 영역이다.

패턴을 만드는 연산

정규 표현식의 핵심은 연결, 선택, 반복이다.

연결(Concatenation): ab — a 다음에 b가 이어진다.
선택(Alternation): a|b — a 또는 b를 허용한다.
반복(Kleene Star): a* — a를 0번 이상 반복한다.

표현을 넓히는 연산도 자주 사용한다.

a+: a를 1번 이상 반복한다. (a* = aa*)
a?: a가 0번 또는 1번 나타난다. (a|ε)
[a-z]: a부터 z까지의 문자 가운데 하나다.
.: 임의의 한 문자다.
^, $: 문자열의 시작과 끝을 지정하는 앵커다.

예를 들어 a*b는 b, ab, aab 등을 매칭한다. (a|b)*abb는 a 또는 b가 반복된 뒤 abb로 끝나는 문자열을 뜻한다. [0-9]+는 10, 256, 999처럼 1개 이상의 숫자를, ^http.*\.com$는 http로 시작하고 .com으로 끝나는 문자열을 표현한다.

⤢✕

정규 표현식으로 나타낼 수 있는 언어를 정규 언어(Regular Language)라고 한다. 이는 유한 오토마타로 인식할 수 있으며 문맥 자유 언어의 부분 집합이다. 정규 언어는 합집합, 연결, Kleene 스타뿐 아니라 교집합과 여집합에 대해서도 닫혀 있다.

정규 표현식에서 NFA를 구성하는 방법

Thompson's Construction은 각 연산자를 작은 NFA 조각으로 만들고, ε-전이로 이를 이어 붙이는 귀납적 구성 방법이다.

기본 기호 a는 다음과 같이 표현할 수 있다.

⤢✕

빈 문자열 ε도 하나의 전이로 구성한다.

⤢✕

연결 ab에서는 앞 조각의 끝과 뒤 조각의 시작을 ε-전이로 잇는다.

⤢✕

선택 a|b는 새 시작 상태에서 각 분기로 ε-전이하고, 두 경로를 하나의 종료 상태로 합친다.

⤢✕

반복 a*는 입력을 소비하지 않고 종료할 수 있는 경로와, a를 읽은 뒤 다시 반복 지점으로 돌아가는 경로를 함께 둔다.

⤢✕

(a|b)*abb는 a와 b의 선택 NFA를 만든 뒤 반복 구조로 감싸고, abb를 연결해 구성할 수 있다. 인식 결과를 단순화하면 다음 상태 전이로 볼 수 있다.

⤢✕

NFA 상태 집합을 DFA 상태로 바꾸기

부분집합 구성법(Subset Construction)은 NFA의 여러 활성 상태를 하나의 DFA 상태로 묶는다. 절차는 ε-closure 계산에서 시작한다. 각 상태에서 ε-전이만으로 도달할 수 있는 상태 집합을 구하고, NFA 시작 상태의 ε-closure를 DFA의 시작 상태로 사용한다.

어떤 부분집합 {q1, q2, ...}에서 입력 a를 받으면 각 qi의 a 전이 결과를 합집합으로 모은 뒤, 그 집합의 ε-closure를 계산한다. NFA의 최종 상태를 포함하는 부분집합은 DFA에서도 최종 상태가 된다.

가령 NFA 상태 {q0, q1, q2}에서 다음 전이가 있다고 하자.

δ(q0, a) = {q1}
δ(q1, ε) = {q1, q2}

DFA 상태 {q0}가 a를 받으면 결과는 다음과 같다.

δ({q0}, a) = ε-closure({q1}) = {q1, q2}

NFA에 n개 상태가 있으면 DFA는 최대 2^n개 상태를 가질 수 있다. 실제 구성에서는 도달 가능한 상태만 생성하지만, 일부 정규 표현식에서는 지수적 상태 폭발이 발생한다. 필요한 상태만 만드는 Lazy 구성, 중복 상태를 합치는 DFA 최소화, NFA와 DFA를 섞는 접근이 이를 다루는 방법이다.

DFA에서 정규 표현식으로 되돌리기

상태 소거법(State Elimination)은 시작 상태와 최종 상태를 제외한 상태를 차례로 제거하면서, 제거한 상태를 경유하던 경로를 정규 표현식으로 합성한다. 마지막에는 시작 상태에서 최종 상태로 가는 정규 표현식만 남는다.

다음 DFA를 생각해 볼 수 있다.

q0 --a--> q1 --b--> q2 (최종)
q1 --a--> q1

q1을 소거하면 q0 --a(a)*b--> q2가 되고, 결과 정규 표현식은 a(a)*b 또는 aa*b다.

GNFA(Generalized NFA)는 전이에 정규 표현식을 둘 수 있도록 확장한 NFA다. DFA를 GNFA로 바꾼 뒤 상태를 소거하면 전이의 정규 표현식이 조합되어 최종 표현식을 얻는다.

엔진 선택은 기능과 실행 특성의 교환이다

백트래킹 방식은 NFA를 직접 시뮬레이션하며, 비결정적 선택 지점에서 가능한 경로를 탐색한다. 재귀나 스택으로 구현할 수 있고 역참조, lookahead 같은 정규 표현식 확장 기능을 지원한다. 다만 최악의 경우 지수 시간 복잡도가 발생하며, 악의적인 정규 표현식으로 ReDoS 공격을 받을 수 있다.

(a+)+b를 aaaa...X에 매칭하면 지수적 백트래킹이 발생해 성능이 저하될 수 있다.

DFA 방식은 정규 표현식을 DFA로 변환한 뒤 결정적인 경로를 따라 실행한다. 선형 시간 복잡도 O(n)으로 동작하므로 성능을 예측하기 쉽고 ReDoS 공격에 안전하며 고속 패턴 매칭에 적합하다. 대신 상태 폭발로 메모리 사용량이 커질 수 있고, 순수 정규 표현식 밖의 확장 기능에는 제약이 있다.

하이브리드 구현도 사용된다. JIT 컴파일은 런타임에 정규 표현식을 네이티브 코드로 컴파일하는 방식이며 V8, PCRE2 등이 이에 해당한다. Thompson NFA 시뮬레이션에 중간 결과 캐싱을 결합하는 방식은 RE2 엔진(Google)에서 사용된다.

패턴 매칭이 쓰이는 지점

컴파일러와 인터프리터의 어휘 분석기는 키워드, 식별자, 리터럴 같은 토큰을 정규 표현식으로 정의하고 NFA와 DFA 변환을 이용한다. Lex/Flex, ANTLR이 여기에 속한다.

식별자는 다음 패턴으로 표현할 수 있다.

[a-zA-Z_][a-zA-Z0-9_]*

정수 리터럴의 한 표현은 다음과 같다.

[1-9][0-9]*|0

⤢✕

grep, sed, awk는 파일 검색과 치환, 로그 분석, 데이터 추출에 정규 표현식을 사용한다. 이메일 주소를 추출하는 명령은 다음과 같다.

grep -E '[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}' file.txt

웹 애플리케이션에서는 이메일, 전화번호, URL 형식 검사와 HTML 폼 유효성 검사에 쓰인다. 한국 전화번호 형식의 예시는 다음과 같다.

/^01[0-9]-[0-9]{3,4}-[0-9]{4}$/;

Express.js, Django 등의 URL 라우팅에서도 경로 패턴을 매칭한다.

app.get("/user/:id([0-9]+)", handler);

네트워크 보안에서는 IDS가 패킷 페이로드의 시그니처를 매칭하고, Snort와 Suricata는 DFA 기반의 고속 패턴 매칭을 활용한다. 방화벽의 URL 필터링과 악성 코드 시그니처도 같은 맥락에 있다.

표현할 수 없는 구조와 확장 문법

균형 잡힌 괄호 { ( [ ] ) }나 HTML/XML 태그 매칭처럼 중첩된 구조에는 Context-Free Grammar가 필요하다. a와 b가 같은 개수로 나타나는 a^n b^n 역시 정규 표현식으로 표현할 수 없다.

Pumping Lemma는 정규 언어의 필요조건으로, 특정 길이 이상의 문자열에는 반복 가능한 부분이 존재해야 함을 이용해 비정규 언어를 증명한다.

정규 표현식 엔진의 확장 기능 중에는 정규 언어의 범위를 넘는 것도 있다. (a+)b\1의 역참조(Backreference)는 같은 패턴을 다시 참조하며 백트래킹 엔진에서 지원된다. (?=pattern)의 앞쪽 탐색과 (?<=pattern)의 뒤쪽 탐색도 순수 정규 표현식은 아니다.

패턴과 상태 수를 줄이는 방법

공통 접두사가 있는 (abc|abd)는 ab(c|d)로 바꾸어 표현할 수 있다. 캡처가 필요하지 않다면 (?:...) 같은 비캡처 그룹을 사용하고, ^, $ 앵커로 불필요한 탐색 범위를 줄일 수 있다.

DFA에서는 Hopcroft's Algorithm으로 동등한 상태를 병합해 최소 상태 DFA를 만든다. 이 알고리즘의 시간 복잡도는 O(n log n)이다. 정규 표현식의 구조와 엔진의 실행 방식을 함께 이해하면, 기능 요구와 성능 제약에 맞는 패턴 매칭 시스템을 설계할 수 있다.