초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.
회원 가입 폼에 들어온 휴대폰 번호가 010-1234-5678 형식인지 확인하려면 어떻게
할까요? 유한 오토마타로 판단할 수는 있지만 상태와 화살표를
하나하나 그려야 합니다. 이런 패턴을 한 줄의 글자로 적을 수는 없을까요?
정규 표현식(regular expression)은 문자열의 패턴을 적는 작은 언어입니다. 줄여서 정규식이라고도 합니다. 대부분의 글자는 그 글자 그대로를 뜻하고, 몇 개의 기호만 특별한 뜻이 있습니다.
| 기호 | 뜻 | 예 | 맞는 문자열 |
|---|---|---|---|
[ ] | 안의 글자 중 하나 | [0-9] | 0, 5, 9 |
| | 둘 중 하나 | cat|dog | cat, dog |
* | 앞의 것이 0번 이상 | ab* | a, ab, abbb |
+ | 앞의 것이 1번 이상 | ab+ | ab, abbb |
? | 앞의 것이 있거나 없거나 | colou?r | color, colour |
{n} | 앞의 것이 정확히 n번 | [0-9]{4} | 2026 |
( ) | 여러 글자를 하나로 묶기 | (ab)+ | ab, abab |
처음의 휴대폰 번호 형식은 010-[0-9]{4}-[0-9]{4}로 적습니다.
[0-9]+ 예시에서 +를 지워 봅시다.정규식으로 적을 수 있는 패턴은 모두 유한 오토마타로 만들 수 있고, 그 반대도
됩니다. 글자를 차례로 적는 것은 화살표를 잇는 것이고, |는 한 상태에서 갈라지는
화살표, *는 되돌아오는 화살표입니다.
지금 상태: q0 · 거부
정규식 ab*c에 문자열 전체가 맞지 않습니다.
ab*c에서 a, b, b, c를 차례로 눌러 봅시다.(0|1)*01에서 아무렇게나 누르다가 0, 1로 끝내 봅시다.그러니 유한 오토마타가 못 하는 일은 정규식도 못 합니다. 괄호 짝 맞추기가
대표적입니다. (()())는 짝이 맞고 (()는 맞지 않습니다. 이를 판단하려면 닫히지
않은 여는 괄호의 개수, 곧 깊이를 세야 합니다. 깊이마다 상태를 하나씩 두면
되지만, 상태의 개수는 정해져 있습니다.
지금 상태: 0 · 받아들임
실제 괄호 짝: 맞음
(를 세 번, )를 세 번 눌러 봅시다.(를 다섯 번, )를 다섯 번 눌러 봅시다.셀 수 있는 깊이보다 깊어지면 기계는 넘침 상태에 빠져, 짝이 맞아도 거부합니다. 상태를 더 늘리면 될까요?
증명 글에서 본 귀류법으로 따져 봅시다. 괄호 짝을 언제나 맞게 판단하는,
상태가 n개인 기계가 있다고 합시다. (를 0개부터 n개까지 읽은 n + 1개 순간이
상태 n개에 나뉘니, 어느 두 순간은 같은 상태에 있습니다. 이를테면 두 개와 다섯
개를 읽은 뒤가 같다면, 뒤에 ) 두 개가 올 때 같은 답을 냅니다. 하나는 짝이 맞고
하나는 틀리니 모순입니다. 그러니 괄호 짝을 언제나 맞게 판단하는 유한 오토마타는
없습니다.
괄호 짝을 맞추려면 스택 글에서처럼 필요한 만큼 늘어나는 기억 공간이 있어야 합니다.
0과 1로 된 문자열을 고르는 규칙 넷 가운데 정규 표현식으로 적을 수 있는 것은 하나뿐입니다. 어느 것일까요? 예를 들어 01001에는 01이 두 번, 10이 한 번 나옵니다.