정규 표현식 이론 (regular expression theory)
쉽게 풀면
정규 표현식은 텍스트 편집기나 프로그래밍에서 문자열 패턴을 찾을 때 흔히 사용하지만, 그 뒤에는 엄밀한 수학 이론이 있다. 이론적으로 정규 표현식으로 표현할 수 있는 언어(패턴)의 집합은 유한 오토마타가 인식할 수 있는 언어의 집합과 정확히 일치한다는 것이 증명되어 있다. 이 덕분에 정규 표현식을 유한 오토마타로 자동 변환하여 매우 빠르게(입력 길이에 비례하는 시간에) 매칭을 수행할 수 있다. 다만 괄호의 짝을 맞추는 것처럼 '중첩 구조'를 인식하는 것은 정규 표현식만으로는 원리적으로 불가능하다.
왜 중요한가
정규 표현식 이론은 형식 언어와 오토마타 이론의 가장 기본적인 응용 사례이면서도, 컴파일러의 어휘 분석기, 텍스트 편집기의 검색·치환 기능, 네트워크 침입 탐지 시스템의 패턴 매칭 등 실무 시스템 전반의 이론적 토대를 이루기 때문에 전산학 논문에서 꾸준히 다뤄집니다. 또한 정규 언어가 어디까지 표현할 수 있고 어디서부터는 한계에 부딪히는지를 규명한 결과는 촘스키 위계 전체를 이해하는 출발점이 되므로, 계산 복잡도 이론이나 프로그래밍 언어 이론의 기초로도 자주 인용됩니다.
논문에서는 이렇게 쓰입니다
컴파일러의 어휘 분석 단계나 텍스트 패턴 매칭 도구의 이론적 기반을 설명할 때 쓰인다.
이 문장은 보안 분야에서 위협 패턴을 정규 표현식으로 정의한 뒤, 이를 오토마타로 변환해 빠르게 매칭하는 시스템을 설계했다는 뜻으로, 정규 표현식 이론이 언어학적 처리를 넘어 보안 시스템 구현에도 활용됨을 보여줍니다.
조금 더 깊게 보면
정규 표현식을 실제로 처리할 때는 비결정론적 유한 오토마타(NFA)로 먼저 변환한 뒤, 이를 다시 결정론적 유한 오토마타(DFA)로 바꾸는 과정을 거치는 것이 일반적입니다. NFA는 상태 전이가 여러 갈래로 나뉠 수 있어 표현이 간결하지만 그대로 실행하기는 비효율적이며, DFA로 변환하면 각 입력 문자에 대해 상태가 하나로 정해져 매우 빠른 매칭이 가능해집니다. 다만 실무에서 널리 쓰이는 정규 표현식 엔진(PCRE 등)은 역참조나 전방탐색 같은 확장 기능을 지원하는데, 이런 기능은 순수한 정규 언어의 범위를 벗어나 이론적으로는 정규 표현식이 아니라는 점도 함께 언급됩니다.
주의할 점
정규 표현식으로는 임의 깊이로 중첩된 괄호나 태그 짝맞추기 같은 문맥 의존적 구조를 표현할 수 없으며, 이런 경우 문맥 자유 문법이 필요하다.