NFA의 DFA 변환 및 ε-전이

NFA를 DFA로 변환

1. ε-전이가 있는 NFA를 DFA로 변환

2. ε-전이가 없는 NFA를 DFA로 변환

* ε-전이 -> 입력 없이 이동 가능한 경로

 

ε-전이가 있는 NFA를 DFA로 변환

- 이 변환은 ε-closure를 이용하여 변환

- NFA에서 의미가 같은 여러 상태들이 DFA에서 하나의 상태로 변환된다는 것

 

ε-closure

어떤 상태에서 ε 전이만 따라갔을 때 도달할 수 있는 모든 상태들의 집합 (시작 상태 포함)

= 간단하게, ε만 타고 갈 수 있는 모든 상태를 한 번에 묶은 것

 

1. S가 한 개의 상태일 경우

- ε-closure(S)는 NFA의 상태 S와 상태 S로부터 레이블이 ε인 간선으로 도달될 수 있는 모든 상태들의 집합

- 이 방법은 ε-closure(S)의 원소가 변하지 않을 때까지 반복

 

2. S가 하나 이상의 상태 집합으로 되어 있는 경우

- ε-closure(S)는 NFA의 상태 S 안에 있는 모든 상태에 대해 1.과 같은 방법으로 집합들을 구하여 합집합한 것

- ε-closure(S) = S에 속하는 모든 x에 대해 ε-closure(x) 합집합

 

  

ε-closure 계산하기

(a+b)*abb 를 인식하는 NFA의 상태 전이도

이 상태 전이도로부터 ε-closure 구하기 (말 그대로 ε-전이만 따라가면 됨)

ε-closure(0) = {0, 1, 2, 4, 7, 8}

ε-closure(1) = {1, 2, 4}

ε-closure(3) = {1, 2, 3, 4, 6, 7, 8}

ε-closure(5) = {1, 2, 3, 4, 6, 7, 8}

ε-closure(9) = {9, 10}

ε-closure(11) = {11, 12}

 

 

ε-전이가 있는 NFA를 DFA로 변환하는 법

입력: ε-전이가 있는 NFA

출력: ε-전이가 있는 NFA와 동등한 DFA

방법

1. ε-NFA의 시작 상태 q0에 대해 ε-closure(q0)를 구하고, ε-closure(q0)를 DFA의 시작 상태로 놓음

2. DFA의 시작 상태를 집합 Ds에 넣음

3. 집합 Ds에 있는 상태에 대해서 ε-NFA에 있는 ε를 제외한 각각의 입력 기호에 대해 도달할 수 있는 상태 집합을 각각 T1, T2, ... 라 한다. 그리고 ε-closure(T1), ε-closure(T2)...를 구하여 이를 DFA의 새로운 상태로 만들어 Ds에 추가한다.

(만약 새로운 상태들이 이미 만들어진 상태와 같은 집합이면 DFA의 새로운 상태로 만들지 않고 현재 상태로부터 이전에 만들어진 상태로 입력 문자에 따른 간선만 만든다.) 지금 적용한 상태를 Ds에서 제거한다.

4. 집합 Ds가 공집합이 될 때까지 3.을 반복

5. 만들어진 상태 중 ε-NFA의 최종 상태를 포함하는 상태들은 모두 DFA의 최종 상태가 된다

 

텍스트로는 이해하기가 쉽지 않으니, 위에 있는 NFA로 해보자

1. ε-NFA의 시작 상태 0

- ε-closure(0)가 DFA의 시작 상태

- ε-closure(0) = {0, 1, 2, 4, 7, 8} = A라 하자

 

2. Ds = {A}

 

// 위에 간선에 a, b 있어야 하는데 빼먹음

3. ε-NFA에 있는 ε를 제외한 입력 기호 -> a랑 b

- a랑 b에 의해 도달할 수 있는 상태들을 구하기 .. a: 3, 9   b: 5

- 정확히는 A에 있는 상태에서 a, b 간선이 있는 걸 구해야 함 (그래서 b에 11이 안됨)

- ε-closure(3, 9) = {3, 6, 1, 2, 4, 7, 8, 9, 10} = B

- ε-closure(5) = {1, 2, 3, 4, 6, 7, 8}  = C

- Ds = {A, B, C} -> Ds = {B, C}     // 이미 처리한 A는 빼주는 거

 

4. Ds = {B, C} 가 공집합이 아니니 알고리즘 되풀이

- B 상태에서 a: 3, 9 b: 5, 11

- ε-closure(3, 9) = {3, 6, 1, 2, 4, 7, 8, 9, 10} = B

- ε–closure{(5, 11)} ＝ {5, 6, 7, 8, 1, 2, 4, 11, 12} = D

- B는 이미 만들어져 있으니 간선만 추가

- Ds = {C, D}

- C 상태에서 a: 3, 9   b: 5 ... 똑같은 방식

 

5. Ds = {D}

- a: {3, 9} b: {5, 13}

- ε–closure{(5, 13)} = {5, 6, 7, 8, 1, 2, 4, 13} = E

- Ds = {E}

 

6. Ds = {E}

- a: {3, 9} b: {5}

- 둘 다 이미 있던 것들(B, C)

- Ds는 공집합

- ε-NFA 최종 상태 13을 포함하는 DFA의 상태는 E .. E가 DFA의 최종 상태

 

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

상태전이표, A가 시작 상태 E가 최종 상태

 

---

ε-전이가 없는 NFA를 DFA로 변환하는 방법

NFA에 의해서 인식되는 언어를 L이라 하면 L을 인식하는 DFA가 존재함

L을 인식하는 NFA, M = ( Q, Σ, δ, q0, F )라 하면

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

- Q' = 2^Q .. Q'의 한 상태는 [q1, q2, ..., qi]의 형태로 표시  (단 qj ∈ Q (단, j = 1, 2, ..., i))   -> NFA 상태 집합 Q의 모든 부분 집합

- F' = {q ∈ Q’ | q는 M의 최종 상태를 포함하는 Q’안에 있는 모든 상태들의 집합}     -> DFA의 종료 상태 집합은 NFA의 종료 상태를 하나라도 포함하는 집합들

- q0' = [q0]         -> 입력 기호의 시작 상태는 동일

- δ({q1, q2, ..., qi}, a) = {P1, P2, ..., Pj}라 하면

- δ'({q1, q2, ..., qi}, a) = [P1, P2, ..., Pj] 이다   -> DFA의 전이 함수 = NFA의 move 결과를 집합 단위로 계산

* [] 안에 있는 건 하나의 DFA 상태로 본다는 뜻 ... (간단히, Q 부분집합으로 나올 수 있는 거 다 한다는 뜻)

 

입력 문자열의 길이에 대한 수학적 귀납적 증명?

• 기초 단계 (길이 0)
  입력이 ε (빈 문자열)일 때 두 오토마타가 같은 결과를 낸다.
• 귀납 가정 (길이 k일 때 성립한다고 가정)
  길이 k인 입력 문자열 w에 대해
  NFA와 DFA가 같은 상태 집합에 도달한다고 가정한다.
• 귀납 단계 (길이 k+1)
  w 뒤에 한 글자 a를 붙인 문자열 wa에 대해서도
  δ’의 정의(즉, move와 부분집합 구성을 통한 전이)를 이용하면
  NFA와 DFA가 동일한 상태 집합을 따라간다는 것을 보인다.

따라서 모든 문자열 길이에 대해,
DFA가 NFA와 동일한 수용(accept/reject) 결과를 낸다는 게 증명된다.

 

실제로 해보자

NFA M = ( {q0, q1}, (0, 1), δ, q0, {q1} )

δ	0	1
q0	{q0, q1}	{q0}
q1	∅	{q0, q1}

상태전이도는 이렇게 되고

 

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

Q' = { [q0], [q1], [q0, q1] }

q0' = [q0]

F' = {[q1], [q0, q1]}

δ' :

δ'( [q0], 0 ) = δ( {q0}, 0 ) = {q0, q1} = [q0, q1] => 이걸 하나의 상태로 봄

δ'( [q0], 1 ) = δ( {q0}, 1 ) = {q0} = [q0]

δ'( [q1], 0 ) = δ( {q1}, 0 ) = f

δ'( [q1], 1 ) = δ( {q1}, 1 ) = {q0, q1} = [q0, q1]

δ'( [q0, q1], 0 ) = δ( {q0, q1}, 0 ) = /*합집합처리*/ {q0, q1} = [q0, q1]

δ'( [q0, q1], 1 ) = δ( {q0, q1}, 1 ) = {q0, q1} = [q0, q1]

 

δ'	0	1
[q0]	[q0, q1]	[q0]
[q1]	∅	[q0, q1]
[q0, q1]	[q0, q1]	[q0, q1]

q0를 A, q1을 B, [q0, q1]을 C라 하고 상태 전이도를 그리면

그런데 B는 도달 불가능한 상태임. 제거 가능

 

이렇게 됨

 

---

 

ε-전이가 없는 NFA를 ε-closure를 이용하여 DFA 변환도 가능함

바로 위에서 한 예제에 적용하면

ε-NFA 시작 상태는 q0..

 

ε-closure(q0) = {q0} = A

Ds = {A}

 

1: ε-closure{(q0, q1)} = {q0, q1} = C

0: ε-closure(q0) = A

Ds = {C}

 

1: ε-closure{(q0, q1)} = {q0, q1} = C

0: ε-closure{(q0, q1)} = {q0, q1} = C

간선만 추가하고 끝, Ds는 이제 공집합

q1 포함하는 상태는 C, 최종 상태는 C

결과적으로 이거 그리면 위에서 그린 거랑 똑같음