[오토마타] 4. 정규표현식(Regular Expression)

정규표현식

우리는 언어를 "1로 시작하는 문자열" 혹은 "1이 짝수번 들어가는 문자열" 등으로 주절주절 표현했다. 좀 더 편리하고, 수학적으로 표현하는 방법은 없을까? 앞서 배운 3가지 기본 연산, union, concatenation, Kleene star을 이용해서 표현할 수 있다. 어떤 정규표현식 R이 표현하는 언어는 $\mathcal{L}(R)$ 이라고 표기하고, 정규표현식 R의 언어(language of R)라고 부른다.

• {1이 딱 한 번 들어가는 문자열} = $\mathcal{L}(0^*10^*)$
• {최소 1이 한 번 들어가는 문자열} = $\mathcal{L}(\{0,1\}^*1\{0,1\}^*)$
• {짝수 길이의 문자열} = $\mathcal{L}((\Sigma\Sigma)^*)$

 

이게 정규표현식이다. 좀 더 수학적으로, 정규표현식의 연역적인 정의를 표현할 수 있다.

1. Σ의 각 심볼과 ε : 이 때, 정규표현식 $a \in \Sigma$ 혹은 ε는 각각 $\mathcal{L}(a) = \{ a \}, \mathcal{L}( \epsilon ) = \{ \epsilon \}$임을 의미한다.
2. $\phi$ : $\mathcal{L}(\phi) = \phi $ 를 의미한다.
3. $R_1, R_2$가 정규표현식이라면, $R_1 \cup R_2$
4. $R_1, R_2$가 정규표현식이라면, $R_1 \circ R_2$
5. $R_1$가 정규표현식이라면, $R_1 ^*$

헷갈리기 좋은 아래의 예시들을 고민해보자.

• $R \cup \phi = R $
• $R \circ \epsilon = R $
• $R \circ \phi = \phi $
• $R \cup \epsilon \neq R $

---

 

정규표현식과 NFA의 동등성

우리는 앞서, 같은 언어를 인식하는 두 오토마타를 동등하다(equivalent)고 정의하고, NFA는 항상 동등한 DFA를 가짐을 증명했다. 이로써, NFA로 표현 가능한 언어는 정규 언어(regular langauge)임을 유도했다. 그리고, 우리는 정규표현식과 NFA의 동등성을 보일 것이다.

정규표현식의 언어를 인식하는 유한 오토마타 M이 존재한다. 또, 유한 오토마타 M이 인식하는 언어는 정규표현식으로 표현가능하다.

"또"를 기준으로 전자와 후자의 명제를 각각 증명해보자.

 

정규표현식 -> FA

앞서, 정규표현식를 5가지 케이스로 나누어 연역적으로 정의했다. 기본적인 1, 2번 케이스의 정규표현식과 동등한 오토마타를 만든다면 증명이 끝난다. 왜냐하면, 정규언어는 union, concatenation, Kleene star에 대하여 닫혀있다는 사실을 이전에 증명했기 때문이다. 이미 $R_1, R_2$가 정규언어라면 $R_1 \cup R_2 $도 정규언어이기 때문에, 1, 2번 케이스의 정규언어들이라는 전제만 확인하면 3,4,5번 케이스는 이걸로 증명이 끝난다. 그리고, $\mathcal{L}(a), \mathcal{L}(\epsilon), \mathcal{L}(\phi) $는 아래의 오토마타들과 동등하다.

Figure 1, $\mathcal{L}(a),  \mathcal{L}(\epsilon),  \mathcal{L}(\phi) $를 인식하는 오토마타들, 출처 [2]

 

FA -> 정규표현식

본격적으로 어려운 증명이다. 어떤 오토마타를 정규표현식으로 변환하는 알고리즘을 찾을것이다. 우리의 목표 오토마타 M에서 목표 정규표현식 R을 구하는 여정에는, 또 새로운 개념이 등장한다. GNFA를 소개한다.

 

 GNFA(Generalized NFA)는 알파벳 심볼 a나 $\epsilon$대신 정규표현식에 의해 전이가 일어나는 NFA다. NFA처럼 문자열을 입력받지만, NFA처럼 매 전이마다 하나의 심볼만 읽을 필요는 없다. NFA 이기 때문에 어느 상태로부터 뻗어나오는 화살표가 동일한 정규표현식을 가져도 괜찮다.

 그리고 편의상, 우리가 다룰 GNFA들은 추가적인 특징을 갖는다. 항상 시작 상태 $q_\text{start}$와 유일한 최종 상태 $q_\text{accept}$를 가진다. 그리고 모든 두 상태 사이에는 서로를 가리키는 화살표가 존재한다. 스스로 뻗어나온 곳으로 들어가는 loop도 모든 상태에서 반드시 존재한다. 단, $q_\text{start}$에서는 뻗어나가는 화살표만 있는 반면, $q_\text{accept}$에는 들어가는 방향의 화살표만 있다.

Figure 2. GNFA의 예시, 출처 [2]

다시 우리의 목적으로 돌아가자. 우리는 어떤 오토마타 M과 동등한 정규표현식을 구하는 법을 찾고 있다. 이제 GNFA를 알았으니, 그 방법을 소개할 수 있다.

1. k개의 상태를 가진 유한 오토마타를 k+2개의 상태를 가진 GNFA로 변환한다. 더해진 2개는 $q_\text{start}$와 $q_\text{accept}$이다.

2. k+2개의 상태의 GNFA에서 $q_\text{start}$, $q_\text{accept}$를 제외한 상태들 중 하나를 제거하여, k+1개의 상태의 GNFA로 치환한다.
$\to$k+1개의 상태의 GNFA를 k개의 상태를 가진 GNFA로 치환한다.
$\to$...
$\to$$q_\text{start}$, $q_\text{accept}$ 2개의 상태만 남을때까지 계속 상태들을 제거하며 새로운 GNFA를 만든다.

3. $q_\text{start}$에서 나와 $q_\text{accept}$로 들어가는 화살표의 정규표현식이 우리가 찾는 정규표현식 R이 된다.

Figure 3. 3-state DFA로부터 정규표현식을 얻기까지. 출처 [2]

1과 2의 과정을 좀 더 자세히 살펴보자.

 

1. DFA -> GNFA

GNFA는 다음과 같이 엄격하게 정의된다.

$
\begin{aligned} & G = (Q, \Sigma, \delta, q_\text{start}, q_\text{accept}), where \\\\ & \delta \text{ is a transition function }(Q - {q_\text{accept}}) \times (Q - {q_\text{start}}) \to R, \\ & \qquad R\text{ is collections of all regular expression over } \Sigma \end{aligned}
$

DFA M으로부터 GNFA G를 아래와 같이 만들면, $L(M)=L(G)$가 된다.

$
\begin{aligned} & \text{G accepts string }w=w_1w_2...w_k \text{ and the sequence of states }q_0,q_1,...,q_k\\\\ & Then, \\ & \text{1. } q_0 = q_\text{start} \\ & \text{2. } q_k = q_\text{accept]} \\ & \text{3. For each } i (0 \lt i \lt k), w_i \in L(R_i) \text{ where }R_i \text{ is the expression on arrow }q_{i-1} \to q_i, \text{or }\delta(q_{i-1}, q_i) \end{aligned}
$

 

2. GNFA의 상태 제거하기

어떻게 GNFA의 상태를 제거할 수 있을까? Figure 4를 보자. $q_\text{rip}$이 우리가 제거할 상태이고, $q_i$와 $q_j$는 그 $q_\text{rip}$과 연결된 상태이다. $q_i$에서 나와 $q_\text{rip}$을 거쳐 $q_j$에 도달하는 방법은 $R_1R_2^*R_3$로 표현된다. 이것을 곧장 $q_i$에서 $q_j$로가는 $R_4$와 union으로 합치면 된다. GNFA의 가능한 모든 상태쌍 $(q_i, q_j)$에 대해 해당 치환을 끝마치면, 마침내 $q_rip$은 삭제해도 되는 상태가 된다.

Figure 4. GNFA의 상태 제거하기

k개의 상태를 가진 G가 $q_\text{start}$, $q_\text{accept}$ 2개의 상태만을 가진 CONVERT(G)가 되기까지의 과정을 알고리즘으로 포함하면 아래와 같다. 살펴보면, CONVERT(G)는 내부에서 CONVERT 함수를 다시 호출하는 재귀적인 형태로 정의되었다.

CONVERT(G):
1. $k$ 는 $G$의 상태 개수.
2. $k = 2$; $G$ 는 시작/최종 상태만을 포함하며, 그 둘 사이는 정규표현식 $R$로 전이된다. 이 $R$을 반환한다.
3. If $k > 2$, $q_{\text{start}}$ 나 $q_{\text{accept}}$ 가 아닌 아무 상태 $q_{\text{rip}} \in Q$를 잡는다. 그리고 GNFA $(Q', \Sigma, \delta', q_{\text{start}}, q_{\text{accept}})$를 잡는다.
1. $Q' = Q - \{q_{\text{rip}}\}$
2. 어떤 $q_i \in Q' - \{q_{\text{accept}}\}$와 어떤 $q_j \in Q' - \{q_{\text{start}}\}$에 대하여
$\quad\delta'(q_i, q_j) = (R_1)(R_2)^*(R_3) \cup (R_4)$
$\quad$이 때, $R_1 = \delta(q_i, q_{\text{rip}})$, $R_2 = \delta(q_{\text{rip}}, q_{\text{rip}})$, $R_3 = \delta(q_{\text{rip}}, q_j)$, $R_4 = \delta(q_i, q_j)$
4. CONVERT(G')를 반환한다.

 

처음 목표했던 유한 오토마타 M에 대하여, $L(M)=L(G)$라는 사실은 보였다. 이제 $L(G)=L(CONVERT(G))$ 라는 사실을 보이면, 마침내 정규표현식과 NFA의 동등성에 대한 증명이 끝난다. 아래에 접어둔 내용을 펼치면 해당 증명을 볼 수 있다.

L(G) = L(G')임을 보이자.

1. $ L(G) \subseteq L(G') \Leftrightarrow \text{If string } w \in L(G), \text{ then } w \in L(G') $

 

가정)

- $G'$은 $G$로부터 상태 $q_k$를 제거하여 얻은 GNFA, $ w \in L(G) $

- $w=w_1...w_l$의 computation history 로부터 $r_0,...,r_l$의 상태들의 배열이 나타남

i) $q_k$가 이 상태들의 배열안에 없으면, G'에서도 똑같은 경로로 w를 수용가능. $ w \in L(G') $는 성립.

ii) $q_k$가 이 상태들의 배열에 있으면,

  - 배열 안의 연속된 $q_k$ 부분배열 $r_a,...,r_b$를 잡는다. ($r_a=...=r_b=q_k$)
  - 그러면, $r_{a-1} \rightarrow q_k$로 가는 레이블: $\delta(r_{a-1}, q_k)$
  - $q_k \rightarrow q_k$로 가는 레이블들: $\delta(q_k, q_k)$ (여러 번 반복 가능)
  - $q_k \rightarrow r_{b+1} $로 가는 레이블: $ \delta(q_k, r_{b+1})$
  - 따라서, $ w_a...w_{b+1} $은 $\delta(r_{a-1}, q_k)\cdot\delta(q_k, q_k)^*\cdot\delta(q_k, r_{b+1}) $ 으로 표현 가능, 그리고 이것은 우리가 새로 잡은 $\delta'(r_{a-1}, r_{b+1})$과 일치한다. 그러면, 이 때도 $ w \in L(G') $.

 

2. $ L(G) \supseteq L(G')  \Leftrightarrow \text{If string } w \in L(G'), \text{ then } w \in L(G) $

- G'에 대하여 (1에서는 G) $w=w_1...w_l$의 computation history 로부터 $r_0,...,r_l$의 상태들의 배열이 나타남

- $w_i=\delta'(r_{i-1},r_i)$이고, $\delta'(r_{i-1},r_i)=\delta(r_{i-1},r_i) \cup \delta(r_{i-1},q_k)\cdot\delta(q_k,q_k)^*\cdot\delta(q_k,r_i)$

i) 만약 G에도 $r_{i-1} \to r_i$ 간선이 그대로 있다면, $w_i \in L(\delta(r_{i-1}, r_i))$ 이므로 w_i를 유지

ii) 아니라면, $w_i$를 $x_1, ..., x_m$으로 분할 후,

- $x_1 \in \delta(r_{i-1},q_k)$

- $x_j \in \delta(r_{q_k},q_k), 2 \leq j \lt m$ 

- $x_m \in \delta(q_k, r_i)$

이제 G'의 computation history로부터 G의 computation history를 얻을 수 있음.

 

출처

[1] John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, 3rd Edition, 2006, Pearson/Addision-Wesley.

[2] Michael Sipser, Introduction to the Theory of Computation, 2nd Edition (International Edition), 2006, Course Technology.