[형식언어] DFA의 상태수 최소화

동치 관계를 이용한 상태수 최소화

 앞선 포스팅에서 NFA를 DFA로 변환하는 방법을 알아보았다. 그런데 DFA를 만들었을 때, 상태수가 너무 많으면 상태 전이표의 크기가 커져 많은 기억 공간을 차지하게 되고 어휘 분석 프로그램이 복잡해질 수 있다. 이때, 우리는 몇 가지 방법을 이용해 상태수를 줄일 수 있다. 

 

 ω ∈  $Σ^*$에 대해 만약 q₁에서 ω를 다 본 상태가 q₃이고, q₂에서 ω를 다 본 상태가 q₄일 때, q₃, q₄중 하나만 종결 상태에 속하면 q₁은 q₂로부터 구별된다(distinguish)고 한다. 이 정리에 따르면 구별되지 않는 상태들은 같은 형태의 입력 스트링을 인식하므로 모두 합쳐버릴 수 있다. 이것을 동치 관계를 이용해 합치는 방법은 아래와 같다.

 

1. 상태를 종결 상태와 비종결 상태의 두 동치류로 분할한다.

2. 같은 입력 십벌에 대해 서로 다른 동치류로 가는 지시선이 존재하면 또 다른 분할을 하여 새로운 동치류를 만든다. 이를 그 입력에 의해 구별된다고 한다.

3. 2 과정을 더 이상 분할이 일어나지 않을 때 까지 반복한다. 

 

아래 간단한 DFA의 상태수를 최소화해보자.

 먼저 종결 상태와 비종결 상태로 구분해야 한다. 그렇다면 종결 상태 1: {A, F}와 비종결 상태 2: {B, C, D, E}로 구분할 수 있다. 우선 종결 상태 집합부터 살펴보자. 1: {A, F} 집합은 입력 심볼 a를 보았을 때, 자기 자신의 집합 1: {A, F}로 향한다. 1: {A, F}에서 입력 심볼 B를 보면 2: {B, C, D, E}로 향하므로 1: {A, F}는 더 이상 분할되지 않는다. 이제 2: {B, C, D, E}를 보자. 2: {B, C, D, E}는 두 집합으로 분할되는데, {B, E}는 입력 심볼 a를 보면 {B, E}로 향하고 입력 심볼 b를 보면 {C, D}로 향한다. 그리고 {C, D}는 입력 심볼 a를 보면 {C, D}로 향하며 입력 심볼 b를 보면 종결 상태인 1:{A, F}로 향한다. 이렇게 위 DFA에서 상태를 1: {A, F}, 2: {B, E}, 3: {C, D}로 분할 가능하다. 이것을 아래 상태 전이표로 표현 가능하다.

	a	b
1: {A, F}	1: {A, F}	2: {B, E}
2: {B, E}	2: {B, E}	3: {C, D}
3: {C, D}	3: {C, D}	1: {A, F}

 

 이와 같이 초기 5개이던 DFA의 상태수가 3개로 줄었으며, 상태 전이표 역시 간단해졌다. 이것을 상태 전이도로 그려보면 위 전이도보다 더 간단해진 것을 확인할 수 있다.

 

도달 불가능한 상태 삭제

 앞서 살펴본 동치 관계를 이용한 상태수 최소화보다는 확실히 쉽고 간단한 방법이다. 상태 전이도에서 어떤 상태로 들어오는 지시선이 없이 나가는 지시선만 가지고 있는 상태는 도달 불가능한 상태(inaccessiblestate)이다. 이러한 상태 역시 DFA에서 삭제하여 상태수를 더 줄여낼 수 있다.

 

DFA 상태수 최소화

따라서 위 두 가지 방법을 이용한 DFA의 상태수 최소화 방법은 다음과 같다.

1. 도달 불가능한 상태 삭제

2. 동치 관계를 이용해 구별되지 않는 상태들을 하나로 합친 후 최소화하여 유한 오토마타를 구성