[Compiler]NFA -> DFA : Subset Construction Algorithm

본 내용은 아래의 출처에서 본것이고 허락을 맡고 포스트한다.

 

출처 : https://talkingaboutme.tistory.com/category/About%20Study/Compiler

 

지난 시간, 정규 표현식을 NFA로 바꾸는 TCA(Thompson's Construction Algorithm) 에 대해 살펴보았다. 

NFA는 정답을 찾기 위한 모든 경우의 수를 표현한 것이라면, 여기서 확실한 정답을 찾기 위해 DFA로 바꿀 필요가 있다.

 

그렇다면, NFA를 DFA로 어떻게 바꿀 수 있을까?? 그것을 살펴보자.

 

그 전에 이때까지 우리의 과정을 나열하면 아래와 같다.

 

NFA는 나올 수 있는 모든 Finite input set 인 '시그마' 에서 적절한 조합을 뽑아낸 것이고,

DFA는 그것을 하나의 정답 형식으로 뽑아낸 값이다.

 

이 NFA를 DFA로 바꾸기 위해 천천히 진행해보자. 다음 예를 보자

 

Example : s = ab...

 

위 그림과 같이 s는 a와 b의 concatenate된 형태이다. 시작 상태는 0 이므로 이때의 NFA는 {0}이다. DFA로 바꾼다 하더라도 0으로 표현할 것이다. 이 후, a라는 input string을 받게 되면, NFA로 표현할 수 있는 state는 {0, 1} 이 될 것이고, 

DFA로 바꿔도 state 0 에서 나갈 수 있는 상태 전이는 '01' 로만 표현될 것이다.

 

이 후, b라는 input string을 받으면 2가지 branch transition이 발생한다. 그 상태에서 아무 입력도 받지 않더라고(심지어  ϵ만 받더라도) state 2로 바꿀 수 있다. 이 때의 NFA는 {2,3,4,0} 이 될 것이다. 그럼 여기서 DFA는 state 2에서 나갈 수 있는 transition도 2340, 023, 024 .... 등 여러가지고 뽑을 수 있다.

 

위를 토대로, NFA를 DFA로 바꾼다는 것은 어떤 input string이 나왔을때 나올 수 있는 NFA의 요소들로 적절한 DFA의 state를 찾는것이다. NFA로 구성할 수 있는 모든 부분집합들을 뽑아보면, DFA가 어떻게 나올 지 유추할 수 있는 것, 이것이 Subset Construction Algorithm이다. 참고로 NFA의 부분집합 S는 N개의 상태를 포괄하는 형태이고 이를 공식에 따라 2^N-1의 개수로 DFA를 추출할 수 있다.  

 

Subset Construction Algorithm의 시작은 ϵ-closure 에서 시작한다. 즉 빈 string ϵ 로부터 전이할 수 있는 모든 set들이다.

 

아래그림을 통해 이해해보자.

 

S = 2

 

위 그림에서 State 2에서 ϵ로 갈 수있는 상태를 뽑아보면 3, 4 가 바로 있고, 한단계를 거쳐서 0 도 있다. (2 -> 3 -> 0)

그래서 ϵ-closure({2}) = {2,3,4,0} 이다. 물론 closure의 요소가 하나의 집합이 될 수 있다.

 

하지만, 위 과정들은 ϵ에만 맞춘것이고, 다음 문자로 어떤 input string이 나올까 를 가정하면 우리가 원하는 DFA의 진행 방향을 알 수 있다. 

현재 상태에서 ϵ-transition으로 갈 수 있는 set들과 현재 상태에서 어떤 입력을 받을 경우의 set들을 정의하면 된다.

 

ϵ-closure와 move(T,a)가 위의 빨간 글자의 정의이다. move(T,a)는 상태 T에 속해있는 현재 상태 S에서 a를 입력받았을 떄 얻을 수 있는 NFA이다. 이를 이용하여 수식 Dtrans을 정의한다. 

 

  Dtrans(T,a) = ϵ-closure(Move(T,a)) : 상태 T에 속하는 어떤 상태 S에 입력을 a로 받았을 때, ϵ 로 전이할 수 있는 모든 state set

 

예를 들어 살펴보자

(A|B)*ABB                                     바로 아래 '2'가 아니라 '6'

 

여기서 state 0에서 ϵ로 전이 될 수 있는 상태를 표현하면 {0,1,2,4,7} 로 정의할 수 있다. 이것이 ϵ-closure(0)이다. 이것을 a라는 특정 set으로 정의한다. 위의 식을 적용해보면,

 

입력을 A로 받았을 떄, Dtrans(a,A) = ϵ-closure(move(a,A))가 되고, 이것은 ϵ-closure({3,8})과 같다. A를 받는 경우는 

상태 2에서 3으로 넘어갈 떄와, 7에서 8로 넘어갈때 2가지 경우이기 때문이다.

ϵ-closure({3,8}) 은 {1,2,3,4,6,7,8}로 정의할 수 있고 이를 새로운 set b라고 하자.

 

또 입력을 B로 받았을 떄, Dtrans(a,B) = ϵ-closure(move(a,B))이고 ϵ-closure(5)가 된다.

ϵ-closure(5) = {1,2,3,4,6,7,8} 로 정의하고 이를 새로운 set c라 정의한다.

 

이런식으로 계속 가지치기를 해 나가면 된다. (재귀 함수를 생각해보아라) 그러다 어느 순간에 겹치는 set도 나올 것이고 더이상 transition 할 여지도 없게 된다. 이 떄까지 계속 묶어 나가는 방식이 Subset Construction Algorithm이다.

 

나머지 과정은 생략하며, 더 궁금하다면, 출처에 잘 설명되어 있다.

 

이 과정을 통해 DFA Transition Table을 작성할 수 있다.

 

 

이를 이용하여 시작 상태 A로 정의한 경우 다음과 같은 DFA를 그릴 수 있다.

 

 

 

 

결국 DFA로 전체적인 상태수도 줄이며, 불필요한 상태를 사용할 이유가 없어졌다. 이 DFA를 좀 더 줄일 수 있는 방법이 있는데 그것이 Minimal DFA라고  하며 다음 장에서 다루어 보자.