정규 표현식
정규 표현식은 어떤 문자열의 집합을 나타낼 수 있게 해 주는 문자열이다. 정규 표현식은 유한 오토마타를 간단히 나타내는 방법으로 볼 수도 있다.
정규 표현식이란
산술에서는 ·이나 + 같은 기호로 (2 + 3) · 4 같은 식을 만든다. 이 식을 계산하면 수가 나온다. 정규 표현식은 문자와 몇 가지 특수 기호를 늘어놓은 것으로, 예를 들어 a(x ∪ y)와 같으며, 이를 계산하면 (형식) 언어가 나온다. 식 (2 + 3) · 4의 결과는 수 20이고, 정규 표현식 a(x ∪ y)의 결과는 두 문자열 “ax”, “ay”의 집합이다.
앞의 정규 표현식 a(x ∪ y)는 어떻게 계산할까? 각 글자는 사실 그 글자 하나만을 원소로 갖는 집합을 줄여 쓴 것이고, 생략된 곱셈은 문자열의 연접이다. 정규 표현식을 “생략 없이” 다시 쓰면 다음과 같다.
이것을 다음과 같이 계산한다. 합집합 {x} ∪ {y}는 언어 {x,y}가 된다. 언어 {a}와 {x,y}를 연접하면 언어 {ax, ay}를 얻는다.
정규 표현식은 프로그래밍에서 매우 자주 쓰이고, 대부분의 프로그래밍 언어에는 어떤 형태로든 정규 표현식이 구현되어 있다. 예를 들어 사용자가 입력한 텍스트가 어떤 조건을 만족하는지(올바른 이메일 주소인지, 올바른 날짜인지 등) 검사하거나, 텍스트를 바꾸는 데(예를 들어 텍스트에 나오는 URL을 모두 클릭할 수 있는 링크로 바꾸는 데) 쓰인다.
실제로 구현된 정규 표현식은 대개 여기서 설명하는 정규 표현식보다 표현력이 강하고, 문법이 조금 다르며 무엇보다 더 복잡하다.
정규 표현식의 정의
정규 표현식은 어떤 알파벳 Σ 위에서 정의한다. 다음을 정규 표현식이라고 한다.
- a, 여기서 a ∈ Σ. 즉 알파벳의 문자 하나는 정규 표현식이다.
- ϵ: 빈 문자열. 프로그래밍에서는 빈 따옴표 “”로도 쓴다.
- ∅: 정규 표현식은 빈 언어도 나타낼 수 있어야 하므로 빈 언어도 정규 표현식이다.
- (R1 ∪ R2), 여기서 R1, R2는 정규 표현식.
- (R1 ∘ R2), 여기서 R1, R2는 정규 표현식.
- (R∗), 여기서 R은 정규 표현식.
4번의 기호 ∪ 대신 세로 막대 기호 |를 써도 된다. 기호 ∘는 쓰지 않아도 된다. 곱셈 기호인 가운뎃점 ·을 대개 쓰지 않는 것처럼 연접 기호 ∘도 대개 쓰지 않는다. 따라서 정규 표현식 a ∘ (b ∪ c)와 a(b|c)는 같다.
각 연산자는 무엇을 뜻할까?
- ∪ 또는 |는 언어의 합집합을 뜻한다.
- ∘는 언어의 연접을 뜻한다.
- ∗는 언어의 클레이니 폐포를 뜻한다.
예:
- a는 간단한 언어 {a}를 나타낸다.
- a|b는 두 문자열로 이루어진 언어 {a, b}를 나타낸다.
- a ∘ b는 언어 {ab}를 나타낸다.
- a(b|c)d는 언어 {abd, acd}를 나타낸다.
- a(b∗)는 글자 “a”로 시작하고 그 뒤에 글자 “b”가 몇 개(0개도 가능) 이어지는 모든 문자열의 언어를 나타낸다.
- (ab)∗는 모든 문자열의 언어 {ϵ, ab, abab, ababab, …}를 나타낸다.
- 0∗10∗는 1을 하나만 포함하는 모든 이진 문자열의 언어를 나타낸다. (더 엄밀하게는 이 식을 (0∗)1(0∗)로 써야 하지만, 괄호가 없어도 읽을 수 있으면 괄호를 생략해도 된다.)
- Σ∗1Σ∗는 1을 적어도 하나 포함하는 모든 문자열의 언어를 나타낸다.
- (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)∗는 모든 자연수의 언어를 나타낸다.
다음으로 정규 표현식과 유한 오토마타가 동치임을 보인다. 즉 계산 결과가 언어 R인 정규 표현식마다 L(A) = R을 만족하는 유한 오토마타 A가 존재하고, 그 역도 성립한다.
참고 자료
목차: 정규 표현식, 정규 표현식을 오토마타로 바꾸기, 일반화된 비결정적 유한 오토마타, 오토마타를 정규 표현식으로 바꾸기