yeolyi.com성열의 컴퓨터공학

정규 표현식

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

회원 가입 폼에 들어온 휴대폰 번호가 010-1234-5678 형식인지 확인하려면 어떻게 할까요? 유한 오토마타로 판단할 수는 있지만 상태와 화살표를 하나하나 그려야 합니다. 이런 패턴을 한 줄의 글자로 적을 수는 없을까요?

패턴을 글자로 적기

정규 표현식(regular expression)은 문자열의 패턴을 적는 작은 언어입니다. 줄여서 정규식이라고도 합니다. 대부분의 글자는 그 글자 그대로를 뜻하고, 몇 개의 기호만 특별한 뜻이 있습니다.

기호뜻예맞는 문자열
[ ]안의 글자 중 하나[0-9]0, 5, 9
|둘 중 하나cat|dogcat, dog
*앞의 것이 0번 이상ab*a, ab, abbb
+앞의 것이 1번 이상ab+ab, abbb
?앞의 것이 있거나 없거나colou?rcolor, colour
{n}앞의 것이 정확히 n번[0-9]{4}2026
( )여러 글자를 하나로 묶기(ab)+ab, abab

처음의 휴대폰 번호 형식은 010-[0-9]{4}-[0-9]{4}로 적습니다.

예시
정규식 (최대 30자)
문자열 (최대 60자)
맞는 곳
color colour colouur

  1. 예시 버튼을 하나씩 눌러 어느 부분이 칠해지는지 봅시다.
  2. [0-9]+ 예시에서 +를 지워 봅시다.

정규 표현식과 오토마타

정규식으로 적을 수 있는 패턴은 모두 유한 오토마타로 만들 수 있고, 그 반대도 됩니다. 글자를 차례로 적는 것은 화살표를 잇는 것이고, |는 한 상태에서 갈라지는 화살표, *는 되돌아오는 화살표입니다.

정규식
abcq0q1q2
읽은 입력
아직 없습니다

지금 상태: q0 · 거부
정규식 ab*c에 문자열 전체가 맞지 않습니다.

  1. ab*c에서 a, b, b, c를 차례로 눌러 봅시다.
  2. (0|1)*01에서 아무렇게나 누르다가 0, 1로 끝내 봅시다.

정규 표현식이 못 하는 것

그러니 유한 오토마타가 못 하는 일은 정규식도 못 합니다. 괄호 짝 맞추기가 대표적입니다. (()())는 짝이 맞고 (()는 맞지 않습니다. 이를 판단하려면 닫히지 않은 여는 괄호의 개수, 곧 깊이를 세야 합니다. 깊이마다 상태를 하나씩 두면 되지만, 상태의 개수는 정해져 있습니다.

셀 수 있는 깊이 2 (상태 4개)
(()()(, )012넘침
읽은 입력
아직 없습니다

지금 상태: 0 · 받아들임
실제 괄호 짝: 맞음

  1. (를 세 번, )를 세 번 눌러 봅시다.
  2. 셀 수 있는 깊이를 4로 올리고 다시 해 봅시다.
  3. 깊이 4에서 (를 다섯 번, )를 다섯 번 눌러 봅시다.

셀 수 있는 깊이보다 깊어지면 기계는 넘침 상태에 빠져, 짝이 맞아도 거부합니다. 상태를 더 늘리면 될까요?

증명 글에서 본 귀류법으로 따져 봅시다. 괄호 짝을 언제나 맞게 판단하는, 상태가 n개인 기계가 있다고 합시다. (를 0개부터 n개까지 읽은 n + 1개 순간이 상태 n개에 나뉘니, 어느 두 순간은 같은 상태에 있습니다. 이를테면 두 개와 다섯 개를 읽은 뒤가 같다면, 뒤에 ) 두 개가 올 때 같은 답을 냅니다. 하나는 짝이 맞고 하나는 틀리니 모순입니다. 그러니 괄호 짝을 언제나 맞게 판단하는 유한 오토마타는 없습니다.

괄호 짝을 맞추려면 스택 글에서처럼 필요한 만큼 늘어나는 기억 공간이 있어야 합니다.

도전 문제

0과 1로 된 문자열을 고르는 규칙 넷 가운데 정규 표현식으로 적을 수 있는 것은 하나뿐입니다. 어느 것일까요? 예를 들어 01001에는 01이 두 번, 10이 한 번 나옵니다.