6. DFA와 NFA의 동등성

NFA는 한 순간에 여러 State에 있을 수 있고 DFA는 정확히 하나의 State에 있어야 한다. 두 모델의 동등성을 보이려면 NFA의 현재 가능한 State 전체를 DFA의 하나의 State로 표현하면 된다. 이 방법을 Subset Construction 또는 Powerset Construction이라고 한다.

핵심 아이디어

NFA의 State Set이

이면 변환된 DFA의 State는 의 부분집합이다.

DFA State 는 NFA가 현재 또는 에 있을 가능성을 동시에 나타낸다.

ε-transition이 없는 경우

NFA 에서 DFA 를 다음과 같이 만든다.

DFA State Set은 의 도달 가능한 부분이다.
Start State는 이다.
State Set 에서 Symbol 를 읽은 다음 State는

이다.

이면 는 DFA의 Accept State이다.

예제

NFA가 다음 Transition을 가진다고 하자.

가 Accept State라고 한다.

DFA Start State는 이다.

에는 Accept State 가 포함되므로 DFA에서도 Accept State이다.

ε-transition이 있는 경우

Start State부터 ε-transition으로 여러 State에 갈 수 있으므로 DFA Start State는 단순한 가 아니라

이다.

Transition도 Symbol을 읽은 뒤 ε-closure를 다시 적용한다.

이 과정을 통해 ε-transition이 숨겨진 도달 가능성까지 모두 포함한다.

정확성의 직관

입력 Prefix 를 읽은 뒤 DFA가 State Set 에 있다는 것은 NFA가 를 읽은 뒤 도달할 수 있는 모든 State의 집합이 정확히 라는 뜻이다. 이를 String 길이에 대한 Induction으로 증명할 수 있다.

Base Case에서 이면 Start closure가 일치한다. Inductive Step에서는 다음 Symbol에 대한 NFA의 모든 Transition을 Union하고 closure를 적용하므로 가능한 State가 정확히 보존된다.

State Explosion

NFA State가 개이면 DFA State 후보는 최대 개이다. 실제로 모두 도달하지는 않을 수 있지만 어떤 Language에서는 지수적으로 많은 State가 필요하다.

이는 NFA가 DFA보다 더 강하다는 뜻이 아니라 같은 정보를 더 압축하여 표현할 수 있다는 뜻이다.

동등성 결론

DFA는 NFA의 특수한 경우이므로 DFA가 인식하는 Language는 NFA도 인식할 수 있다. 반대로 Subset Construction으로 모든 NFA를 DFA로 바꿀 수 있다.

정리

DFA State 하나가 NFA의 State Set을 나타낸다.
Accept State가 하나라도 포함된 Set은 DFA의 Accept State이다.
ε-NFA에서는 매 단계 ε-closure를 적용한다.
NFA와 DFA의 표현력은 같지만 State 수는 크게 달라질 수 있다.

연습 문제

1번

NFA State Set이 이고

일 때 Subset Construction의 다음 DFA State를 구한다.

2번

NFA의 Accept State가 일 때 다음 DFA State 중 Accept State를 모두 고른다.