[오토마타] 3. DFA와 NFA의 동등성

기본 정규 연산

우리는 지금까지, 결정적/비결정적 유한 오토마타의 정의를 배웠다. 앞으로는 오토마타와 정규언어들의 속성들에 대해 다룰 것이다. 그 이전에, 이 속성들을 익히거나 증명하는데에 유용한 도구상자들을 준비했다. 아래의 3가지 연산은 정규 연산(regular operation)이라 불리는 기본적인 언어들 간의 연산이다.

 

어떤 언어 A,B에 대하여 아래처럼 정의된다. Kleene는 클레이니, 클리네 등으로 발음하는 듯 하다.

 

우리는 자연수 $\times$ 자연수가 자연수라는 사실을 알고 있다. 이것을 수학에서는 자연수가 곱셈에 대하여 닫혀있다(closed)고 말한다. 마찬가지로, 정규언어는 위 3가지 기본 정규 연산에 대하여 닫혀있다. 예를 들어, 정규언어와 정규언어의 union은 정규언어다. 달리 말하면, 어느 두 언어가 유한오토마타로 표현된다면, 그 두 언어의 정규연산 결과를 표현하는 유한오토마타도 반드시 존재한다. 어떻게 증명할까? 각 정규언어 A,B를 인식하는 유한오토마타 $M_1,M_2$를 이용해서, $A \cup B, A \circ B, A^{*}$을 인식하는 유한 오토마타 M을 만들수 있다면, 증명이 완료된다. 더 엄밀하게는, 그렇게 만들어진 유한 오토마타 M이 정말 $A \cup B, A \circ B, A^{*}$를 인식하는지 정당성(correctness)을 검증하는 과정을 보이면 증명이 완료된다.

 

Union의 닫힘성(closure)을 증명해보자. 두 정규언어 A,B를 인식하는 $N_1$과 $N_2$ NFA를 이용하여, $A \cup B$를 인식하는 $N을 만든다면 아래 Figure 4의 왼쪽처럼 만들 수 있다. 오른쪽은 그것을 수학적으로 표현한 것이다.

Figure 4. Closure of Union, 왼쪽 출처[2]

 

$A \circ B$와 $A^{*}$도 Figure 5에서 간단히 소개하고 넘어간다.

Figure 5. $A \circ B$ 왼쪽, $A^{*}$ 오른쪽, 출처[2]

---

 

NFA와 DFA의 동등성

같은 언어를 인식하는 두 유한 오토마타를 우리는 동등하다(equivalent)고 한다. 신기하게도 모든 NFA는 항상 동등한 DFA를 갖는다. 그말인즉슨, 어떤 언어 L을 인식하는 NFA는 똑같은 언어를 인식하는 DFA로 항상 치환할 수 있다는 것이다. 아래와 같은 방식으로 증명한다.

1. 어떤 언어 L을 인식하는 NFA $N=(Q,\Sigma,\delta,q_0,F)$로부터 같은 언어 L을 인식하는 DFA $M=(Q',\Sigma',\delta',q_0',F')$을 만든다. 이 때, NFA의 ε 전이를 허용하지 않는 경우에서 허용하는 경우로 생각을 발전시킨다.

2. 새로 만든 M이 정확히 언어 L을 인식한다는 정당성(correctness)을 증명한다. 먼저, $L(N) \subseteq L(M) \Leftrightarrow w \in L(N) \text{ then } w \in L(M)$를 증명한다.

3. 2의 반대 방향을 증명한다. $L(N) \supseteq L(M)  \Leftrightarrow w \in L(M) \text{ then } w \in L(N)$

 

1의 증명 - ε가 없는 경우

$
\text{From an NFA N}=(Q,\Sigma,\delta,q_0,F), \text{ construct a DFA M} =(Q',\Sigma,\delta',q_0', F') \text{ s.t. } L(N)=L(M) \\

\begin{aligned}

& \text{1. } Q' = 2^Q, \text{which is power set of Q}\\
& \text{2. } \Sigma = \Sigma \\
& \text{3. } q_0'={q_0} \\
& \text{4. } F'\subseteq 2^Q \text{ and } F'=\{f|f \cap F \neq \phi \} \\
& \text{5. } \delta'(R,a) = \bigcup_{r \in R}^{}\delta(r,a) \text{ for every } R \in 2^Q \text{ and every symbol } a \in \Sigma

\end{aligned}
$

1의 증명 - ε가 있는 경우
앞서 설명했던 ε-closure를 활용한다. 이때, $ext(X) = \bigcup_{q \in X}^{}ext(q)$로, 집합에 대해서도 정의를 확장하여 사용하였다.

$\text{From an NFA N}=(Q,\Sigma,\delta,q_0,F), \text{ construct a DFA M} = (Q',\Sigma,\delta',q_0', F') \text{ s.t. } L(N)=L(M) \\
\begin{aligned}

& \text{1. } Q' = 2^Q, \text{which is power set of Q}\\
& \text{2. } \Sigma = \Sigma \\
& \text{3. } q_0'=ext(q_0) \\
& \text{4. } F'\subseteq 2^Q \text{ and } F'=\{f|f \cap F \neq \phi \} \\
& \text{5. } \delta'(R,a) = ext(\bigcup_{r \in R}^{}\delta(r,a)) \text{ for every } R \in 2^Q \text{ and every symbol } a \in \Sigma

\end{aligned}$

2의 증명

N의 정의로부터 M을 만든것 처럼, 어떤 문자열 w을 N에 넘겼을 때의 accepting computation history로부터, M의 computation history를 만든다. 그 후, 만든 M의 computation history 최종 결과가 최종 상태(final state)임을 보이면, 즉 accepting 임을 보이면 된다.

$

\begin{aligned}
& \text{Let }w=y_1y_2...y_s \text{ for } y_i \in \Sigma \\
& \text{ and let accepting computation history of N for w, } \\
& \pi = (q_0,w=w_0), (r_1,w_1), ... (r_i,w_i),...,(r_s,w_s=\epsilon) \\
& \text{Then, }r_0 \in ext(\{q_0\}) \text{ and } r_i \in ext(\{\delta(r_{i-1},y_i)\}) \text{ for every i} \\
& \text{And, }r_s\in F \\\\

& \text{Now, construct computation history for w in DFA M} \\
& \pi' = (Q_0,w=w_0), (Q_1,w_1), ... (Q_i,w_i),...,(Q_s,w_s=\epsilon) \\\\

& Then, \\
& \bullet\, Q_0 = \{q_0\} \\
& \bullet\, r_1 = \delta(q_0,y_1) \text{ and } Q_1 = ext(\delta(Q_0,y_1)), r_1\in Q_1\\
& \bullet\, \text{Inductively, } r_i \in Q_i \\
& \bullet\, \text{Finally, } r_s \in Q_s \text{ which means }\pi' \text{accepting computation history}

\end{aligned}
$

 

3의 증명

$
\begin{aligned}
& \text{Let }w=y_1y_2...y_s \text{ for } y_i \in \Sigma \\
& \text{ and let accepting computation history of M for w, } \\
& \pi' = (R_0,w=w_0), (R_1,w_1), ... (R_i,w_i),...,(R_s,w_s=\epsilon) \\
& \text{By definition, } R_i=\delta'(R_{i-1},y_i) \\\\

& \text{Now, construct computation history for w in NFA N} \\
& \pi = (q_0,w=w_0), (q_1,w_1), ... (q_i,w_i),...,(q_s,w_s=\epsilon) \\\\

& Then, \\
& \bullet\, \text{There exists }q_s, \text{ s.t. } q_s \in F \text{ and } q_s \in R_s\\
& \bullet\, \text{There exists }q_{s-1}\text{ s.t. } \delta(q_{s-1},y_s)=q_s \text{ and } q_{s-1} \in R_{s-1}\\
& \bullet\, \text{Inductively, } q_i \in R_i \\
& \bullet\, \text{Finally, } q_0 \in R_0

\end{aligned}$

 

이제 우리는 모든 NFA는 동등한 DFA를 가짐을 알았다. DFA로 표현가능한 언어를 우리는 정규 언어라고 부른다. 즉, 아래의 결론을 얻었다.

NFA가 인식하는 언어는 정규 언어다.

 

출처

[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.