DFA의 상태수 최소화

DFA의 상태수 최소화(state minimization)

- DFA를 이용하는 어휘분석기의 상태 전이표의 크기를 줄임

- 기억 공간을 적게 차지하도록 하고 어휘분석 프로그램을 간단히 하는데 큰 도움

- 상태수를 최소화하는 방법: 동치관계(equivalance relation)를 이용 상태수에 합침(state merge)

 

구별 가능(distinguishable)

- 문자열 w ∈ Σ* 에 대해, 만약 q1 상태에서 w를 모두 본 상태가 q3고 q2에서 w를 모두 본 상태가 q4일 때, q3, q4 중 하나만 종결 상태에 속하면 2개의 상태 q1과 q2는 구별 가능하다고 함

 

구별 불가능(Indistinguishable)

- 문자열 w ∈ Σ* 에 대해, 만약 q1 상태에서 w를 모두 본 상태가 q3고 q2에서 w를 모두 본 상태가 q4일 때, q3, q4가 모두 종결 상태에 속하거나 모두 종결 상태가 아니라면 2개의 상태 q1과 a2는 구별 불가능하다고 함

 

DFA 상태수 최소화 알고리즘

입력: 하나의 DFA M

출력: M과 동일한 언어를 수용하고 가능한 한 적은 상태수를 갖는 하나의 DFA M'

방법

1. 시작 상태로부터 도달 불가능한 상태를 모두 제거

2. 초기의 동치관계인 최종 상태(final state)와 최종 상태가 아닌 것(non-final state)의 두 동치류(equivalance class)로 분할(partition)

3. 하나의 동치류 안에서 같은 입력 기호에 대해 서로 다른 동치류로 가는 간선이 존재하면 또 다른 분할을 하여 새로운 동치류를 만듦

4. 3.의 과정을 반복하여 더 이상 새로운 분할이 일어나지 않을 때까지 반복

5. M의 최종 상태에 속하는 상태가 동치류 속에 있으면 해당 동치류는 M'의 최종 상태

 

최소화된 DFA M' = ( Q', Σ', δ', q0', F' ) 는 다음 조건을 만족

(1) Q' : 동치류의 집합으로서 Q'의 한 상태를 [q]로 표시 .. 의미는 상태 q를 포함하는 동치류

(2) [P], [q]를 임의의 동치류라 하고 δ(P, a) = q 이면 δ'([P], a) = [q]

(3) q0' = [q0]

(4) F' = { [q] | q ∈ F }

 

역시 이 글만 보고 어떻게 동작하는지 알긴 어렵다.

예제를 보자

 

δ	a	b
A	B	C
B	B	D
C	B	C
D	B	E
E	B	C

이 DFA를 최소화 해보자

1. 도달 불가능 상태 없음

2. 최종 상태, 아닌 상태의 두 동치류 .. {E} {A, B, C, D}

3. 각 동치류가 각 입력 기호에 대해 구별되는가를 조사하여 더 이상 분할이 일어나지 않을 때까지 반복

 

입력	동치류 이름	1				2
	동치류	A	B	C	D	E
a		1	1	1	1	1
b		1	1	1	2	1

1번 동치류에서 입력 기호 b에 대해 {D}가 구분됨

정확히 뭘 한 거냐면 a, b가 들어왔을 때 가게 되는 동치류가 1번인지 2번인지 구분한 것

D는 b가 들어올 때 다른 곳으로 가서 구별 가능해진 것

 

입력	동치류 이름	1			2	3
	동치류	A	B	C	D	E
a		1	1	1	1	1
b		1	2	1	3	1

이러면 입력기호 b에 대해 {A, C}와 {B}가 구별됨

 

입력	동치류 이름	1		2	3	4
	동치류	A	C	B	D	E
a		2	2	2	2	2
b		1	1	3	4	1

이제 각 동치류는 더 이상 구분되지 않음

DFA의 최종 상태 E, 그러니까 이거 포함하는 {E} 동치류가 M'의 최종상태

{A, C} 를 X, {B}를 Y, {D}를 Z, {E}를 W라 하면 

DFA M' = ( Q', Σ', δ', q0', F' )

Q' = {X, Y, Z, W}

Σ' = {a, b}

δ	a	b
X	Y	X
Y	Y	Z
Z	Y	W
W	Y	X

q0' = X

F' = {W}

상태수가 5개에서 4개로 줄음

 

최종적으로 상태전이도는 이렇게 표현됨