Regular Expressions

상위 문서: Regular Languages

개요

정규 표현식(regular expression)은 문자열에서 특정한 패턴을 찾거나 치환·검증하기 위해 사용하는 표현식이다.

Formal Definition of Regular Expressions

정규 표현식 집합 ${ℛ}{ℰ}$는 알파벳 집합 $\mathrm{\Sigma }$에 대해 아래의 닫힘 조건(closure conditions)을 만족하는 최소 집합을 의미한다:

1. $a\in {ℛ}{ℰ},\mathrm{\forall }a\in \mathrm{\Sigma }$
2. 빈 문자열 $ϵ$에 대해, $ϵ\in {ℛ}{ℰ}$
3. 어떤 문자열도 포함하지 않는 공집합 $\mathrm{\varnothing }$에 대해, $\mathrm{\varnothing }\in {ℛ}{ℰ}$
4. Union: If $R_1\in {ℛ}{ℰ},R_2\in {ℛ}{ℰ}$, then $(R_1\cup R_2)\in {ℛ}{ℰ}$
5. Concatenation: If $R_1\in {ℛ}{ℰ},R_2\in {ℛ}{ℰ}$, then $(R_1\circ R_2)\in {ℛ}{ℰ}$
6. Kleene Star: If $R_1\in {ℛ}{ℰ}$, then $(R_1*)\in {ℛ}{ℰ}$

이때 정규 표현식은 단순히 문자열(strings)이며, $\{\mathrm{\varnothing },ϵ,(,),\cup ,\circ ,*\}\cup \mathrm{\Sigma }$라는 알파벳 집합 위에서 정의된다. 따라서, $a\cup b$라는 정규표현식이 문자열로 해석되어 단순히 알파벳 $a,\cup ,b$의 조합인지, 혹은 정규표현식 $a,b$의 합집합으로 해석되는지는 맥락에 따라 달라진다.

Structural Induction for RE

어떤 성질 P(R)이 모든 정규 표현식 R에 대해 성립함을 보이고 싶다면 먼저, 아래와 같은 기본 케이스를 규정해야 한다:

1. $P(a),\mathrm{\forall }a\in \mathrm{\Sigma }$ 
2. $P(ϵ),P(\mathrm{\varnothing })$

이를 바탕으로 두 ${ℛ}{ℰ}{R}_1,R_2$에 대해 $P(R_1),P(R_2)$가 성립한다고 가정하면, 아래도 성립함을 보인다:

1. $P(R_1\cup R_2)$
2. $P(R_1\circ R_2)$
3. $P((R_1*))$

이 과정을 거치면 P(R)은 모든 정규 표현식 R에 대해 참이라는 결론을 얻을 수 있다.

The Language Denoted by a Regular Expression

아래는 정규 표현식 R이 나타내는 언어 L(R)을 귀납적으로 정의한 것이다:

• $L(a)=\{a\}$ → 단일 문자열 { "a" }.
• $L(\mathrm{\varnothing })=\mathrm{\varnothing }$ → 아무 문자열도 없음.
• $L(ϵ)=ϵ$ → 오직 빈 문자열 하나만.
• $L(R_1\cup R_2)=L(R_1)\cup L(R_2)$
• $L(R_1\circ R_2)=L(R_1)\circ L(R_2)$ → R1의 문자열과 R2의 문자열을 이어붙여 생성.
• $L(R_1*)=(L(R_1))*$ → R1이 만드는 문자열들의 0번 이상의 반복.

Simplifying Operators

연산자 우선순위를 설정하여 괄호를 생략할 수 있는데, 그 순서는 $\cup <\circ <*$(Kleene Star)와 같다. 또한 $\circ$ 기호를 생략하여 보통 문자열 처럼 붙여 쓸 수 있다. 따라서, $01*$과 같은 정규 표현식은 $0\circ (1*)$과 같다. 또한 아래는 복잡한 정규 표현식을 단순화한 예시이다.

$R\equiv (0\cup (1\cup (0(((0\cup 1)*)0))\cup (1(((0\cup 1)*)1))))$
$R\equiv 0\cup 1\cup 0(0\cup 1)*0\cup 1(0\cup 1)*1$

위의 예시는 사람이 읽기에 훨씬 편하도록 R을 만든 것이다. 이는 연산자 우선순위 규칙과 괄호 생략 규칙을 도입한 이유이다. ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$