[오토마타] 5. 정규 언어의 성질(미완성)

이 글은 정규언어의 다양한 성질들에 대해 배운다. 첫째로, 다룰 것은 정규 언어라면 항상 성립하는 pumping lemma이다. 이 것을 통해, 우리는 어떤 언어가 정규언어인지 아닌지 쉽게 증명할 수 있다. 둘째는, 정규 언어의 닫힘성(closure)이다. 앞서, union, concatenation, Kleene star의 닫힘성을 보였듯이, 더 많은 연산자에 대한 닫힘성을 살펴본다. 셋째로, 두 오토마타의 동등성을 비교하는 방법에 대해 알아본다.

Pumping Lemma

어떤 정규언어 A에 대해, 항상 상수 p(pumping length라고 부름)가 존재하여:
- 길이가 p 이상인 A의 모든 문자열 w는
- w를 $w=xyz$ 세 부분으로 나눌 수 있고,
- 다음 조건을 만족한다.

1. $|y| \ge 1 $
2. $|xy| \le p $
3. 모든 $0$ 이상의 i에 대해 $xy^iz \in A$

다소 난해하게 느껴질 수 있지만, 이 pumping lemma는 정규언어라면 항상 만족하는 성질이다. 그래서, 어떤 언어가 정규언어가 아님을 증명할 때 아주 유용하다. Pumping Lemma의 증명 이전에, 예제를 살펴보자.

 

Q. B = $\{0^n1^n|n \ge 0\}$이 정규언어가 아님을 보이시오.

1. 모든 p에 대해서,

2. w의 길이가 p 이상이도록, $w=0^p1^p$라고 잡자.

3. 그러면 $|y| \ge 1 $, $|xy| \le p $를 만족하는 모든 w=xyz 세 부분으로의 분할에서, y는 항상 $0^i$로 표현된다. $(i \ge 1)$

4. 그러면 $xy^2z=0^{p+i}1^p$가 되므로, $xy^iz \notin B$가 되는 어떤 $i$가 존재한다. 

5. Pumping lemma에 의해서, B는 정규언어가 아님!

 

직관적으로도 $0^n1^n$은 0의 개수에 따라 무한하게 많은 상태가 준비되어야 하므로, 유한 오토마타로 표현이 불가능함을 알 수 있지만, pumping lemma를 통해 수학적으로 엄밀하게 증명했다. Pumping Lemma를 이용하면 어떤 언어가 정규언어가 아님을 이렇게 보일 수 있다. 

 

Pumping Lemma의 증명에는 비둘기집 원리를 이용한다.

Figure 1. Proof of Pumping Lemma, 출처 [1]

$ xyz $는 문자열 $w$를 분할한것이다. 그림에서도 알 수 있듯이 문자열이 $xyz$가 아니라 $xz$, $xy^2z$, ..., $xy^nz$ 들로 y를 pumping 해도 모두 오토마타가 인식하는 언어일 것이다. 그런데, 충분히 길이가 긴 문자열에 대해서, y와 같은 사이클은 항상 존재한다! FA의 상태의 개수는 유한하므로, 상태의 전체 개수보다 길이가 긴 computation history에는 적어도 하나의 상태는 두 번 방문하게 되기 때문이다. 첫 방문과, 두번째 방문 사이가 그림의 y처럼 사이클을 이룬다. 이런 상황을 만드는 pumping length p는 항상 존재한다.

 

정규 언어에 대한 닫힘성(Closure)들

1. 두 정규 언어의 합집합(Union)은 정규언어다.
2. 두 정규 언어의 교집합(Intersection)은 정규언어다.
3. 어느 정규 언어의 여집합(Complement)은 정규언어다.
4. 두 정규 언어의 차집합(Difference)은 정규언어다.
5. 어느 정규 언어의 역(Reversal)은 정규언어다.
6. 어느 정규 언어의 Kleene Star 연산결과는 정규언어다.
7. 두 정규 언어의 결합(Concatenation)은 정규언어다.
8. 어느 정규 언어의 Homomorphism 연산 결과 정규언어다. (어떤 심볼 하나를 문자열로 치환)
9. 어느 정규 언어의 Inverse Homomorphism 연산 결과 정규언어다. (어떤 문자열을 다른 심볼 하나로 치환)

 

정규언어는 위 연산들에 대하여 닫혀있다. 위 연산들의 닫힘성을 엄밀하게 증명하는 요령은 모두 동일하다. 일단, 두 정규 언어를 인식하는 오토마타 $M_1, M_2$를(혹은 $M$ 하나를) 정의하고, 그 성분들을 활용해서 새로운 오토마타 $M'$을 정의하면 된다. 그리고, 그 오토마타 $M'$이 정말 우리가 원하는 연산결과가 맞다는 정당성(correctness)을 보이면 된다. 기존 오토마타가 수용하는 $w=w_1w_2...w_n$이 이 문자열이 $M'$에서도 최종상태(final state)로 도착함을 보이는 것이다. 이미 이전 글에서 동일한 증명을 소개한 바 있다.

 

두 오토마타의 동등성

두 오토마타가 동등(equivalent)하다는 것은, 두 오타마타의 언어가 같다는 것을 의미한다고 이전 글에서 소개했다. 주어진 두 오토마타가 동등한지 어떻게 알 수 있을까? 우리는 어떤 오토마타와 동등하되, 기존 오토마타보다 상태를 줄인 오토마타를 구하는 방법을 배울것이다. 그리고, 지금 소개할 마법같은 과정은 주어진 오토마타의 상태를 가능한 최소로 줄인 minimum-state 오토마타를 구한다. 신기하게도, 이 마법의 과정을 거쳐 나오는 오토마타의 minimum-state는 유일하다. 그래서, 서로 다른 오토마타들의 각각의 minimum-state 오토마타를 구했는데, 그 결과가 같다면 두 오토마타는 동등한 것이다. 두 오토마타가 동등한데, minimum-state 오토마타가 다르게 나오는 일은 없다.

 

상태들의 동등성

어느 오토마타에 서로 다른 두 상태 $p,q$에 대하여 아래의 동시에 조건을 만족하면 p와 q는 동등하다(equivalent) 혹은 구분불가능(indistinguishable)하다고 한다. 

- $\hat{\delta(p,w)} \in F$ 인 모든 w에 대하여 $\hat{\delta(q,w)} \in F$.
- 역도 성립.

 

만약 문자열 w가 어떤 상태는 최종상태로 보내고, 나머지 상태는 보내지 않아서 위 조건의 반례가 되는 경우, w가 p와 q를 구분한다(distinguish)고 한다. 예를 보면 이해하기 쉽다.

Figure 2. Example for Indistinguishable States. 출처[1]

위 다이어그램에서 A와 E를 보자.
- 문자열 "1"은 A도 E도 최종상태인 C로 보내지 않는다. 그러므로, "1"은 A와 E를 구분하지 않는다.
- 문자열 "0"이나 $\epsilon$도 A와 E를 구분하지 않는다.
- 문자열 "01"은 A와 E 모두 최종상태인 C로 보낸다. 그러므로, "01"도 A와 E를 구분하지 않는다.
- 사실 모든 문자열은 A와 E를 동시에 최종상태로 보내거나, 동시에 보내지 않는다. 그래서, A와 E는 동등하다.
- 마찬가지로, B와 H도 동등하다.
- 한편, "0"은 A를 최종상태로 보내지 않지만, B는 최종상태로 보내므로, A와 B는 동등하지 않다.

 

우리는 존재하는 모든 두 상태들끼리의 동등성을 알고 싶기 때문에, 이것을 체크하는 표를 만들것이다. 구구단의 표처럼 가로세로축에 모든 상태들이 포함된 2차원의 표이다. 대신 $p=q$인 경우는 의미가 없고, p와 q가 동등하면, 당연히 q와 p도 동등하므로 표 절반만 채우면 된다. 만약 상태가 5개 있는 오토마타라면, 전체 25칸중 5칸은 제외하고, 그 절반인 10칸을 채우면 되는것이다. 아래는 그 과정이다.

1. $q_0$에서 어떻게 해도 도달할수 없는 상태들을 지운다.(들어가는 화살표가 없는 상태)
2. 일단, $F$에 속하는 상태와 와 $Q-F$에 속하는 상태는 동등할수 없으므로 X라고 표시한다.
3. 어떤 심볼 a에 대하여, $\delta(p,a)$와 $\delta(q,a)$가 X로 표시되어 있으면, $(p,q)$도 X표시한다.
4. 더 이상 X표시 할게 없을떄까지 반복한다.
5. 남은 것은 모두 동등하다.

이제 동등한 것 끼리 묶음을 구할 수 있다. 예를 들어 Figure 2의 오토마타에 이 과정을 수행하면 Figure 3과 같다. 이 표를 통해서 $\{A,E\}, \{,B,H\},\{D,F\}$가 각각 서로 동등하다는 것을 알 수 있다. 동등한 것을 하나의 블럭(block)으로 생각하면, A~H는 $\{A,E\},\{B,H\},\{C\},\{D,F\},\{G\}$ 5개의 블럭으로 나눠진 분할(partition)이라고 볼 수 있다.

Figure 3. The Table of Distinguishability, 출처[1]

 

오토마타의 동등성

Figure 4. Equivalence of Automata, 출처 [1]

Figure 4의 왼쪽의 두 오토마타는 동등하다. 두 오토마타를 하나의 오토마타로 생각하고(시작 상태가 두 개인 오토마타라는게 말이 안되긴 하지만), 오른쪽 그림의 동등성 표를 완성한다. 이를 통해 A와 C가 동등함을 알 수 있다. 그런데 어느 두 오토마타의 시작 상태가 동등하다는 것은 두 오토마타가 동등하다는 것을 의미한다! 왜냐하면 그말인즉슨, A를 최종상태로 보내는 어떤 문자열 w는 C도 최종상태로 보낸다는 뜻이고, 역도 성립할 것이며, 그것은 두 오토마타의 언어가 같다는 말과 같기 때문이다.

 

오토마타의 최소화(Minimization)

다시 Figure 3의 분할 ${A,E},{B,H},{C},{D,F},{G}$를 논의로 데려오자. 우리는 이 분할의 각 블럭들을 하나의 상태로 생각하고 새로운 오토마타를 만들 수 있다. 기존 오토마타의 시작상태와 최종상태는 $A$와 $G$였으므로, 새로운 오토마타의 시작블럭도 $\{A,E\}$와 $\{G|}$로 한다. 전이들도 기존 오토마타들의 전이를 그대로 합치면 된다.

Figure 5. Minimization of Automata, 출처 [1]

 

 

어떤 DFA로부터 이 과정을 거쳐 만들어진 새로운 DFA는 기존 DFA와 항상 동등하다. 또, 이렇게 만들어진 DFA보다 더 적은 종류의 상태를 가진 동등한 DFA는 없다. 달리 말하면, 이렇게 만들어진 DFA 상태 개수는 최소다. 왜 그런지 해소되지 않은 의문들을 정리해본다.

 

이 과정 전후의 오토마타가 동등한가?

이 오토마타가 정말 최소개수의 상태를 갖는가?

최소 오토마타는 유일한가?

동등하지만 서로 다른 DFA로부터 각각 이 과정을 거쳐 만든 최소 DFA는 항상 같을까?

Myhill-Nerode