정규 표현식(Regular expression)

정규 표현식은 문자열의 모양을 적는 짧은 식입니다. 글자 a는 문자열 a 하나만 뜻하고, 여기에 세 가지 연산을 씁니다. 연결 rs는 r에 맞는 문자열 뒤에 s에 맞는 문자열을 잇고, 선택 r|s는 둘 중 하나에 맞으면 되며, 반복 r*(미국 논리학자 스티븐 클리니의 이름을 따 클리니 스타라 부릅니다)는 r에 맞는 조각을 0번 이상 잇습니다. 식 하나가 뜻하는 것은 문자열들의 집합⁠(set)⁠, 곧 언어이고, 선택은 합집합⁠(union)⁠입니다. 예를 들어 (a|b)*abb는 'a와 b로 된 아무 문자열 뒤에 abb'이니, abb로 끝나는 문자열 전체입니다.

패턴: . 아래 버튼으로 문자열을 만들어 넣어 보세요. a b ⌫ 비우기 입력 의 경로는 입니다.

그림 아래의 판정은 두 번 계산합니다. 한 번은 위의 오토마톤⁠(automaton)⁠을 직접 따라가고, 한 번은 브라우저에 들어 있는 정규 표현식 엔진(JavaScript RegExp)에 패턴을 그대로 넘깁니다. 두 판정은 . 우연이 아닙니다. 1950년대 클리니가 보인 정리에 따르면, 정규 표현식으로 적을 수 있는 언어와 유한 오토마톤이 알아보는 언어는 정확히 같습니다. 식에서 기계로 가는 쪽은 조각마다 작은 기계를 만들어 이어 붙이면 되고(뒤에 나오는 켄 톰프슨의 이름을 딴 톰프슨 구성⁠(Thompson's construction)⁠), 기계에서 식으로 가는 쪽은 상태를 하나씩 없애며 화살표에 식을 적어 나가면 됩니다. 오토마톤 그림은 꼭짓점⁠(vertex)⁠이 상태, 변이 글자인 방향 그래프이고, 받아들여지는 문자열은 시작에서 이중 원까지 가는 길입니다.

식을 기계로 바꾸면 처음에는 한 글자에 여러 갈래로 갈 수 있는 비결정적 오토마톤⁠(nondeterministic automaton)⁠이 나옵니다. 이것을 결정적으로 바꾸는 부분집합 구성⁠(subset construction)⁠에서는 '지금 있을 수 있는 상태들의 집합'을 새 상태로 삼으니, 상태 n개짜리 기계가 최대 $2^n$개, 곧 멱집합⁠(power set)⁠의 크기만큼 불어날 수 있습니다. '끝에서 k번째 글자가 a'라는 패턴은 비결정적 오토마톤으로는 상태 k+1개면 되지만, 결정적 오토마톤으로는 상태가 $2^k$개 꼭 필요합니다. 비결정적 기계는 '여기가 끝에서 k번째다'라고 짐작하는 갈래를 하나 내보내면 그만이지만, 결정적 기계는 입력이 어디서 끝날지 모르니 최근 k글자를 모두 기억해야 하고, a와 b로 된 k글자는 $2^k$가지이기 때문입니다. 보기의 마지막 패턴이 k = 2인 경우로, 상태가 $2^2 = 4$개입니다.

정규 표현식이 못 하는 일도 분명합니다. 기억이 유한하니 aⁿbⁿ이나 짝 맞는 괄호처럼 개수를 끝없이 맞춰야 하는 언어는 적을 수 없고(비둘기집 원리⁠, pigeonhole principle⁠), 이런 언어에는 문맥 자유 문법⁠(context-free grammar)⁠이 필요합니다. 촘스키 위계⁠(Chomsky hierarchy)⁠의 가장 안쪽 층입니다. 다만 프로그래밍 언어의 '정규식'은 되참조⁠(backreference)⁠ 같은 기능을 더해서 이론상의 정규 언어⁠(regular language)⁠를 넘어섭니다. \1은 '첫째 괄호가 맞춘 것과 똑같은 문자열'이라는 뜻이라, (a*)b\1은 b 앞뒤의 a 개수가 같은 문자열 aⁿbaⁿ을 알아봅니다. 그 대가로 속도⁠(velocity)⁠를 보장할 수 없습니다. 되참조가 있는 패턴을 맞추는 일은 NP 완전⁠(NP-complete)⁠ 문제여서, 다항 시간⁠(polynomial time)⁠ 방법이 있다면 P = NP가 됩니다.

이어지는 곳. 뒤에 유닉스 운영체제를 함께 만든 미국 프로그래머 켄 톰프슨이 1960년대 말 문서 편집기에 정규 표현식 검색을 넣었고, 그것이 파일에서 패턴에 맞는 줄을 찾아 주는 유닉스 명령 grep으로 이어졌습니다. 오늘날에는 검색, 입력 검증, 컴파일러⁠(compiler)⁠의 낱말 분석에 두루 쓰입니다. 오탈자를 허락하는 검색은 패턴에 딱 맞는 문자열 대신 패턴과의 편집 거리⁠(edit distance)⁠가 작은 문자열을 찾는 문제입니다. 정규 표현식과 짝을 이루는 오토마톤의 화살표에 확률⁠(probability)⁠을 붙이면 마르코프 연쇄⁠(Markov chain)⁠가 되고, 상태를 숨기면 은닉 마르코프 모델⁠(hidden Markov model)⁠이 됩니다.