[계산이론](5)[DFA와 NFA 사이의 변환]

DFA는 코드로 옮기기 쉽고
NFA는 그리기가 쉽다.
-> 상황에 맞게 DFA, NFA를 변환해야 한다!

 

DFA <-> NFA로의 변환은 항상 존재한다 (DFA equivalent NFA)
다르게 말하면 DFA가 못하는건 NFA도 못하고
NFA가 표현할 수 있는 언어는 DFA도 충분히 할 수 있다.
    즉, NFA로 표현될 수 있는건 regular language다

 

DFA -> NFA

NFA의 정의를 보면 DFA보다 더 큰 범위를 정의하고 있다.
대부분은 똑같지만,
     $\sum_\epsilon$이나
     $r_{r+1}$ ∈ $\delta(r_i, w_{i+1})$
     처럼 DFA의 정의를 이미 포함하고 있다.
DFA -> NFA일때는
     $\sum_\epsilon$에서 $\epsilon$을 안 쓰면 되고,
     $r_{i+1}$은 ${q_1}$처럼 집합모양으로 바꿔주면 된다.

 

NFA -> DFA

• 증명 아이디어
  NFA의 분기를 동시에 따라가볼까?
  분기의 수가 transition에 따라 변동되네?
  분기의 수가많아봐야 |P(Q)|네?
  모든 (2^{상태의 수}) 갯수의 상태를 만들면 되려나?

  ε transition을 신경 쓰지 않을 때

  NFA N = ($Q$, $\sum$, $\delta$, $q_0$, $F$)이라고 할때,
  DFA D = ($Q'$, $\sum'$, $\delta'$, $q_0'$, $F'$) 가 존재함을 보이자
  • Q' = P(Q)
    원래 상태 집합의 멱집합
  • $\sum' = \sum$ (같은 alphabet이라 하자)
  • $\delta'(R, a) = {q\in Q \ | \ a \in \delta(r, a) }$ 단, $R \in Q', r \in R, \ a \in \sum$
    또는 $\delta'(R, a) = \bigcup_{r \in R} \delta(r, a) \ 단, \ r \in R$
    원래 trans에서 되는 경우의 집합
    이때 인자로 q1같은 상태 하나를 받는게 아니라 집합을 받으므로, 집합 내부에서 될 수 있는 모든 경우를 생각해야 함.
  • q0' = {q0}
    이것도 Q'이 집합이므로 집합으로 정의
  • $F' = {R \in Q'\ |\ \exists a \in R, a\in F }$
    또는 F′={R⊆Q ∣ R∩F ≠ ∅}

예) N = ({q1, q2}, {0, 1}, $\delta$, q1, {q2}) 이고, δ(q1, 0) = {q2}, δ(q2, 0) = {q1, q2}, δ(q2, 1) = {q2}가 있을때, DFA로 변환하시오.

- Q' = {∅, {q1}, {q2}, {q1, q2}}
- (알파벳은 동일)
- q0' = {q1}
- F' = {q2를 포함하는 Q'의 원소} = {{q2}, {q1, q2}}
- δ
     δ'(∅, 0) = δ'(∅, 1) = ∅
     δ'({q1}, 0) = {q2}, δ'({q1}, 1) = ∅
     δ'({q2}, 0) = {q1, q2}, δ'({q2}, 1) = {q2}
     δ'({q1, q2}, 0) = {q1, q2}, δ'({q1, q2}, 1) = ∅∪{q2} = {q2}

ε transition을 신경 쓸 때

R이 상태집합의 부분집합일때, E(R)을 R의 원소에서 ε로 trans할 수 있는 집합이라 정의하자.
이떄, ε를 고려한 NFA -> DFA 변환은 아까 전에서

• q0' = E({q0})
• δ'(R, a) = {$q \in Q \ | \ q \in$ E(δ(r, a))}
  이렇게 정의만 살짝 바꾸면 된다.

예) N = ({q1, q2}, {0, 1}, $\delta$, q1, {q2}) 이고, δ(q1, 0) = {q2}, δ(q1, ε) = {q2}, δ(q2, 0) = {q2}, δ(q2, 1) = {q2}가 있을때, DFA로 변환하시오.

- Q' = {∅, {q1}, {q2}, {q1, q2}}
- (알파벳은 동일)
- q0' = E({q1}) = {q1, q2}
- F' = {q2를 포함하는 Q'의 원소} = {{q2}, {q1, q2}}
- δ'
     δ'(∅, 0) = δ'(∅, 1) = E(∅) = ∅
     δ'({q1}, 0) = E({q2}) = {q2}, δ'({q1}, 1) = E(∅) = ∅
     δ'({q2}, 0) = E({q1}) = {q1, q2}, δ'({q2}, 1) = E({q2}) = {q2}
     δ'({q1, q2}, 0) = E({q1, q2}) = {q1, q2}, δ'({q1, q2}, 1) = E({q2}) = {q2}

즉, 이렇게 임의의 NFA를 DFA로 바꿀 수 있음을 알 수 있다.