NFA와 DFA

NFA와 DFA

DFA와 NFA는 서로 동등하다

• DFA보다 NFA가 언어의 구조를 쉽게 표현
• NFA는 DFA보다 프로그램으로 구현하기 어려움
• DFA는 NFA보다 프로그램으로 구현했을 경우에 효율면에서 훨씬 우수

일반적인 구현은 DFA로 해야 되는데 NFA가 언어의 구조를 쉽게 표현할 수 있기 때문에 서로가 변환이 필요하다

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

• DFA를 이용하는 어휘 분석기의 상태 전이표의 크기를 줄임
  • 기억공간을 적게 차지하도록 하고 또한 어휘분석 프로그램을 간단히 하는데 큰 도움
• 상태수를 최소화하는 방법
  • 동치관계(equivalence relation)을 이용 상태수를 합침(state merge)

[정의 3.22] 구별가능(distinguishable)

[정의 3.23] 구별불가능(Indistinguishable)

ε –closure

1. S가 한 개의 상태일 경우
   • ε-closure(S)는 NFA의 상태 S와 상태 S로부터 레이블이 ε 인 간선으로 도달될 수 있는 NFA의 모든 상태들의 집합
   • 이 방법은 ε-closure(S)의 원소가 변하지 않을 때까지 반복
2. S가 하나 이상의 상태 집합으로 되어 있는 경우
   • ε-closure(S)는 NFA의 상태 S안에 있는 모든 상태에 대해서 1.과 같은 방법으로 집합들을 구하여 합집합한 것
   • 

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

이 변환은 ε–closure를 이용하여 변환한다.
NFA에서 의미가 같은 여러 상태들이 DFA에서 하나의 상태로 변환되는 것을 의미한다.

[입력] ε–전이가 있는 NFA
[출력] ε–전이가 있는 NFA와 동등한 DFA

1. ε–NFA의 시작 상태 q0에 대해 ε–closure(q0)를 구하고 ε–closure(q0)를 DFA의 시작 상태로 놓는다.
2. DFA의 시작 상태를 집합 DS에 넣는다.
3. 집합 DS 에 있는 상태에 대해서 ε–NFA에 있는 ε를 제외한 각각의 입력 기호에 대해 도달 할 수 있는 상태 집합을 각각 T1, T2, ··· 라 한다.
   1. 그런 다음 ε–closure(T1), ε– closure(T2), ··· 를 구하여, 이를 DFA의 새로운 상태로 만들어 집합 DS에 추가한다.
   2. 만약 새로운 상태들이 이미 만들어진 상태와 같은 집합이면, DFA의 새로운 상태로 만 들지 않고 현재 상태로부터 이전에 만들어진 상태로 입력문자에 따른 간선만 만든다.
   3. 지금 적용한 상태를 집합 DS에서 제거한다.
4. 집합 DS 가 공집합이 될 때까지 과정 3)을 되풀이한다.
5. 만들어진 상태 중에서 ε–NFA의 최종 상태를 포함하는 상태들은 모두 DFA의 최종 상태가 된다

NFA와 DFA을 풀이하며 이해해봅시다

ε-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, 4, 5, 6, 7, 8}
ε-closure(9) = {9, 10}
ε-closure(11) = {11, 12}
ε-closure(0, 9) = ε-closure(0) ∪ ε-closure(9)
					= {0, 1, 2, 4, 7, 8, 9, 10} 
ε-closure(5, 11) = ε-closure(5) ∪ ε-closure(11)
					= {1, 2, 4, 5, 6, 7, 8, 11, 12}

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

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

입력 문자열의 길이에 대하여 수학적 귀납법으로 증명이 가능하다

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

[입력] 하나의 DFA M
[출력] M과 동일한 언어를 수용하고 가능한 한 적은 상태수를 갖는 하나의 DFA M‘
[방법]

1. 시작상태로부터 도달 불가능한 상태를 모두 제거
2. 초기의 동치관계인 최종 상태(final state)와 최종상태가 아닌 것(non-final state) 의 두 동치류(equivalence class)로 분할(partition)
3. 하나의 동치류 안에서 같은 입력기호에 대해 서로 다른 동치류로 가는 간선이 존재 하면 또 다른 분할을 하여 새로운 동치류를 만듦
4. 3)의 과정을 반복하여 더 이상 새로운 분할이 일어나지 않을 때까지 반복
5. M의 최종 상태에 속하는 상태가 동치류속에 있으면 이 동치류는 M‘의 최종 상태
   

예제

[예제 3-48] Ε-closure 계산하기

예제 3-30의 정규 표현 (a + b)*abb를 인식하는 NFA를 상태 전이도로 나타내면 다음과 같다.

ε-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, 4, 5, 6, 7, 8} ε-closure(9) = {9, 10}  
ε-closure(11) = {11, 12}  
ε-closure(0, 9) = ε-closure(0) ∪ ε-closure(9)
					= {0, 1, 2, 4, 7, 8, 9, 10} 
ε-closure(5, 11) = ε-closure(5) ∪ ε-closure(11)
					= {1, 2, 4, 5, 6, 7, 8, 11, 12}

[예제 3-49] ε 전이가 있는 NFA를 DFA로 변환하기

[예제 3-48]에 ε - 전이가 없는 NFA를 DFA로 변환을 적용하여 ε-전이가 있는 NFA를 DFA로 변환하자

기본적으로는 NFA를 DFA로 변환하는 방법과 동일하다.
하지만, next state는 도달 가능한 모든 state들의 집합이다

1단계

• 0에서 ε 전이로 갈 수 있는 곳은 {0,1,2,4,7,8}이다.

2단계

• a가 ε-closure(3,9)되는 이유는, 입력 기호 a로 도달하는 곳이 3과 9 밖에 없기 때문이다.
• 같은 이유로 b는 ε-closure(5)가 되는 것이다.
  결론적으로 현재까지의 DFA의 상태 전이도는 아래와 같다
  
  3 단계
  

Ds ={C, D}이므로, 같은 방법으로 C상태에서 입력기호 a, b를 보고 갈수 있는 상태 집합을 구하면 {3, 9}, {5}가 되므로 ε–closure({3, 9})는 B상태이고 ε–closure(5)는 C 상태이다.

그러므로 DFA의 상태 전이도는 다음과 같다.

Ds는 {D}이다.

4단계

5단계

DS가 공집합이므로 ε–NFA의 최종 상태 13을 포함하는 DFA의 상태를 구해 보면 E이므로 E는 DFA의 최종 상태가 된다.

결론 : 상태 전이표
이와 같은 일련의 과정을 상태 전이표로 나타내면 다음과 같다.

핵심은 상태에따라 입력 기호에 따른 다음 상태를 매칭해주면 된다

[예제 3-51] NFA를 DFA로 변환하기 3

[[NFA와 DFA#2. ε - 전이가 없는 NFA를 DFA로 변환|ε - 전이가 없는 NFA를 DFA로 변환]]을 이용하여 ε–전이가 없는 NFA를 DFA로 변환하시오.

이를 상태 전이도로 나타내면 아래와 같다.

이때 NFA를 DFA로 변환해보자. DFA M′ = (Q′, Σ, δ′, q0′, F′)라 하면 ε 전이가 없는 NFA를 DFA로 변환하는 방법에 의해 다음과 같이 된다.

위의 상태 전이 함수를 상태전이 표로 표시하면 다음과 같다.


위의 상태 전이도는 DFA로 바뀌어져 있지만, 시작 상태로부터 도달 불가능한 상태 이므로, 문장을 인식하는데 불필요한 상태가 된다.
그러므로 B 상태는 제거할 수 있으므로, 다음과 같은 상태 전이도를 얻을 수 있다

[예제 3-52] NFA를 DFA로 변환하기 4

[예제 3-51]에 주어진 ε-전이가 없는 NFA를 DFA로 변환하되 [[NFA와 DFA#2. ε - 전이가 없는 NFA를 DFA로 변환| ε - 전이가 없는 NFA를 DFA로 변환]]을 이용하지 않고, ε-전이가 있는 DFA로 변환하는 [[NFA와 DFA#1. ε - 전이가 있는 NFA를 DFA로 변환|ε - 전이가 있는 NFA를 DFA로 변환]]을 적용해보자.

[예제 3-54] DFA의 상태수 최소화하기 1

각 동치류는 더 이상 구별되지 않는다.
마지막으로 DFA의 최종 상태가 E 이므로 E를 포 함하는 모든 동치류는 {E}이므로 {E}가 M’의 최종 상태이다.
그래서 각 동치류 {A, C}, {B}, {D}, {E}를 X, Y, Z, W라 하면 최소화된 DFA M’ = (Q’, ∑’, δ’, q0’, F’) 에서 상태수가 5개에서 4개로 줄었으며 최소화된 DFA를 상태 전이도로 표현하면 아래와 같다

부족한 점이나 잘못 된 점을 알려주시면 시정하겠습니다 :>