Regular Expressions 문서 원본 보기

[[분류:계산 이론 개론]]
[[분류:컴퓨터 공학]]
상위 문서: [[Regular Languages#Regular Expressions|Regular Languages]]

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

==Formal Definition of Regular Expressions==
정규 표현식 집합 <math>\mathcal{RE}</math>는 알파벳 집합 <math>\Sigma</math>에 대해 아래의 닫힘 조건(closure conditions)을 만족하는 최소 집합을 의미한다:
# <math>a \in \mathcal{RE},\,\, \forall a \in \Sigma</math>
# 빈 문자열 <math>\epsilon</math>에 대해, <math>\epsilon \in \mathcal{RE}</math>
# 어떤 문자열도 포함하지 않는 공집합 <math>\empty</math>에 대해, <math>\empty \in \mathcal{RE}</math>
# Union: If <math>R_1 \in \mathcal{RE}, R_2 \in \mathcal{RE}</math>, then <math>(R_1 \cup R_2) \in \mathcal{RE}</math>
# Concatenation: If <math>R_1 \in \mathcal{RE}, R_2 \in \mathcal{RE}</math>, then <math>(R_1 \circ R_2) \in \mathcal{RE}</math>
# Kleene Star: If <math>R_1 \in \mathcal{RE}</math>, then <math>(R_1*) \in \mathcal{RE}</math>
이때 정규 표현식은 단순히 문자열(strings)이며, <math>\{\empty, \epsilon, (, ), \cup, \circ, *\} \cup \Sigma</math>라는 알파벳 집합 위에서 정의된다. 따라서, <math>a \cup b</math>라는 정규표현식이 문자열로 해석되어 단순히 알파벳 <math>a,\cup,b</math>의 조합인지, 혹은 정규표현식 <math>a, b</math>의 합집합으로 해석되는지는 맥락에 따라 달라진다.

===Structural Induction for RE===
어떤 성질 P(R)이 모든 정규 표현식 R에 대해 성립함을 보이고 싶다면 먼저, 아래와 같은 기본 케이스를 규정해야 한다:
 1. <math>P(a), \forall a \in \Sigma</math> 
 2. <math>P(\epsilon), P(\empty)</math>
이를 바탕으로 두 <math>\mathcal{RE}\,\, R_1, R_2</math>에 대해 <math>P(R_1), P(R_2)</math>가 성립한다고 가정하면, 아래도 성립함을 보인다:
 1. <math>P(R_1 \cup R_2)</math>
 2. <math>P(R_1 \circ R_2)</math>
 3. <math>P((R_1*))</math>
이 과정을 거치면 P(R)은 모든 정규 표현식 R에 대해 참이라는 결론을 얻을 수 있다.

===The Language Denoted by a Regular Expression===
아래는 정규 표현식 R이 나타내는 언어 L(R)을 귀납적으로 정의한 것이다:
* <math>L(a) = \{a\}</math> → 단일 문자열 { "a" }.
* <math>L(\empty) = \empty</math> → 아무 문자열도 없음.
* <math>L(\epsilon) = \epsilon</math> → 오직 빈 문자열 하나만.
* <math>L(R_1 \cup R_2) = L(R_1) \cup L(R_2)</math>
* <math>L(R_1 \circ R_2) = L(R_1) \circ L(R_2)</math> → R1의 문자열과 R2의 문자열을 이어붙여 생성.
* <math>L(R_1*) = (L(R_1))*</math> → R1이 만드는 문자열들의 0번 이상의 반복.
이때 아래와 같은 중요한 정리(Lemma)가 존재한다.
  For all regular expressions R the language L(R) is a regular language.
이를 증명하기 위해서는 구조적 귀납법(Structural Induction)을 사용하며, 이를 위해 아래의 명제들을 증명해야 한다:
[[파일:Figure 1. NFA for .png|섬네일|200x200픽셀|Figure 1. NFA for <math>L(a)</math>]][[파일:Figure 2. NFA for.png|섬네일|200x200픽셀|Figure 2. NFA for <math>L(\epsilon)</math>]][[파일:Figure 3. NFA for.png|섬네일|200x200픽셀|Figure 3. NFA for <math>L(\empty)</math>]]
# <math>\forall a \in \Sigma,\,\, L(a)</math> is a regular language.
# <math>L(\epsilon)</math> is a regular language.
# <math>L(\empty)</math> is a regular language.
# <math>L(R1 \cup R2) = L(R1) \cup L(R2)</math> is a regular language.
# <math>L(R1 \circ R2) = L(R1) \circ L(R2)</math> is a regular language.
# <math>L(R1*) = (L(R1))*</math> is a regular language.
먼저, 명제 1, 2, 3들은 figure 1, 2, 3에 제시된 NFA를 통해 나타내어진다. 또한, 정규 언어들은 각 연산에 대해 닫혀(close)되어 있으므로, 명제 3, 4, 5번또한 성립한다고 할 수 있다.

===Simplifying Operators===
연산자 우선순위를 설정하여 괄호를 생략할 수 있는데, 그 순서는 <math>\cup < \circ < *</math>(Kleene Star)와 같다. 또한 <math>\circ</math> 기호를 생략하여 보통 문자열 처럼 붙여 쓸 수 있다. 따라서, <math>01*</math>과 같은 정규 표현식은 <math>0\circ(1*)</math>과 같다. 또한 아래는 복잡한 정규 표현식을 단순화한 예시이다.
 <math>R \equiv (0 \cup(1\cup(0(((0\cup1)*)0))\cup(1(((0\cup1)*)1))))</math>
 <math>R \equiv 0 \cup 1\cup 0(0\cup1)*0\cup1(0\cup1)*1</math>
위의 예시는 사람이 읽기에 훨씬 편하도록 R을 만든 것이다. 이는 연산자 우선순위 규칙과 괄호 생략 규칙을 도입한 이유이다.

==Constructing a RE from a NFA==
모든 정규 언어는 정규표현식으로 표현될 수 있다. 즉, NFA가 주어지면 반드시 동치인 정규표현식이 존재한다. 이는 아래와 같은 정리(Lemma)를 통해 나타낼 수 있다:
 If L is a regular language, then L = L(R) for some regular expression R.
이를 증명하는 방법은 상태 제거 절차(state elimination procedure)이며, 이는 NFA의 상태들을 하나씩 제거하면서, 그 상태를 통과하는 경로들을 정규표현식으로 바꿔가며 단순화하는 것이다. 이때 일반적인 NFA는 각각의 전이(transit)에 해당하는 화살표가 단일 문자(혹은 <math>\epsilon</math>)으로 라벨링되어 있다. 하지만 상태를 제거하다 보면, 두 상태를 연결하는 경로가 단일 문자가 아니라 정규표현식 전체로 표현되는 경우가 생기며, 이를 더욱 쉽게 나타낼 수 있도록 GNFA(Generalized NFA)라는 개념을 도입할 수 있다. 즉, GNFA는 “전이가 단일 문자 대신 정규표현식으로 라벨링된 NFA”를 의미한다. 주어진 NFA를 GNFA로 치환하는 절차를 포함한 GNFA에 대한 자세한 설명은 [[Generalized NFA|GNFA]] 문서를 참조하면 된다.

===Converting GNFA to RE===
GNFA에서 RE를 얻는 절차는 기저 조건과, 재귀적 단계로 나뉜다. 먼저 기저 조건은 아래와 같다:
* 만약 상태가 2개(시작/종료)뿐이면, 답은 <math>\delta(q_{start}, q_{accept})</math>이다.
이는 시작 상태에서 종료 상태로 전이하는 라벨이 곧 정규표현식이라는 것을 의미한다. 재귀적 단계는 아래와 같다:
# 상태가 2개 초과라면, 제거할 상태 <math>q_{rip}</math>을 하나 선택한다. 이때 <math>q_{start}, q_{end}</math>는 제외한다.
# <math>q_{rip}</math>를 제외한 새로운 상태 집합 <math>Q' = Q - \{q_{rip}\}</math>을 정의한다.
# 이에 따라 전이 <math>\delta</math>를 <math>\delta'(q_i, q_j) = R_1(R_2)*R_3 \cup R_4</math>와 같이 재정의한다. 이때 <math>R_1,R_2,R_3,R_4</math>는 아래와 같다:
## <math>R_1 = \delta(q_i, q_{rip})</math>
## <math>R_2 = \delta(q_{rip}, q_{rip})</math>(자신으로 돌아오는 루프)
## <math>R_3 = \delta(q_{rip}, q_j)</math>
## <math>R_4 = \delta(q_i, q_j)</math> 
<math>q_i</math>에서 <math>q_j</math>로 가는 경우는 <math>q_{rip}</math>를 거치는 경우와 아닌 경우 두 가지로 나뉜다. 먼저, <math>R_4 = \delta(q_i, q_j)</math>는 <math>q_i</math>에서 <math>q_j</math>로 <math>q_{rip}</math>을 거치지 않고 전이가 이뤄지는 라벨을 의미한다.<br>
<math>q_{rip}</math>을 거쳐서 가는 경우는 figure 4와 같이 표현된다. 따라서 이와 같은 경우에서 읽어들이는 문자열은 <math>R_1(R_2)*R_3</math>이다. 따라서 두 경로를 합친 전이 라벨은 <math>\delta'(q_i, q_j) = R_1(R_2)*R_3 \cup R_4</math>이다.
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>

==각주==