[형식언어] 비결정적 유한 오토마타

 상당히 오랜만에 돌아온 형식언어 관련 포스팅. 8월에 뭔가 바쁜 일들이 많아서 미루고 미루다가 결국 개강이 1주일밖에 남지 않아버렸다. 기억을 되짚으며 비결정적 유한 오토마타, NFA에 대해 알아보자.

 

비결정적 유한 오토마타

 바로 앞 포스팅에서는 결정적 유한 오토마타인 DFA에 대해 알아보았는데, DFA는 상태 전이 함수의 결과가 1개이다. 즉, 상태 q에서 전이 함수를 거치면 하나의 상태로만 전이된다. NFA는 DFA와 반대로 상태 q에서 전이 함수를 거치면 여러 상태로 전이할 수 있다. 아래의 NFA 예시를 하나 살펴보자.

 

M = ({q₀, q₁, q₂, q₃, q_f}, {0, 1}, δ, q₀, {q_f})

δ	0	1
q0	{q1, q2}	{q1, q3}
q1	{q1, q2}	{q1, q3}
q2	{qf}	∅
q3	∅	{qf}
q4	{qf}	{qf}

 

자, DFA에서도 그래프를 그려보았듯이 위 상태 전이 표를 보고도 NFA의 그래프를 그릴 수 있을 것이다. 그 결과는 아래와 같다.

 

전이 함수의 확장

 인식기를 통해 스트링이 인식된다는 것은 스트링이 유한 오토마타를 거쳐 종결 상태에 도달함을 의미한다고 배웠다. NFA에서는 스트링을 모두 본 후에, 종결 상태가 하나라도 나타나면 해당 스트링은 NFA에 의해 인식됨을 의미한다. 

 

 전이 함수를 확장시켜 보자. 먼저, 입력으로 스트링이 올 수 있도록 하고, 하나의 상태를 여러 상태로 확장해 보자. 글로 쓰기만 하면 조금 어려울 수 있는데 직접 해보면 DFA와 큰 차이가 있지는 않다. 스트링의 가장 왼쪽 심볼을 보았을 때, 왼쪽 심볼을 통해 현재 상태에서 전이 가능한 상태를 모두 기술하면 된다. 이제 스트링 1011이 위 NFA를 사용해 인식 가능한지 알아보자.

 

δ(q0, 1011) = δ({q1, q3}, 011) = δ({q1, q2}, 11) = δ({q1, q3}, 1) = {q1, q3, qf}와 같은 과정으로 스트링 1011은 최종적으로 종결 상태인 qf에 도달할 수 있으므로 위 NFA를 이용하면 인식 가능하다!!

 

 다른 문자열로도 테스트해보자. 이번엔 0100이 위 NFA에서 인식 가능한지 살펴보겠다. 

δ(q0, 0100) = δ({q1, q2}, 100) = δ({q1, q3}, 00) = δ({q1, q2}, 0) = {q1, q2, qf}와 같이 인식되고, 종결 상태 qf가 등장하였으므로 스트링 0100 역시 위 NFA로 확장 가능하다.

 

NFA의 시간 복잡도

 상태의 수 |Q| = m이고, 입력 스트링의 길이가 n이라면, 비결정적 유한 오토마타는 최대 mⁿ의 시간 복잡도를 가진다. 물론 최선의 경우에는 스트링의 심볼을 하나 확인할 때마다 어찌저찌 상태 전이가 잘 되어 스트링의 모든 심볼을 인식한 후 종결 상태로 향한다면 n의 복잡도를 가지지만, CS에서는 최악의 경우를 고려해야 하니 mⁿ의 시간 복잡도는 굉장히 비효율적이다. 시간이 너무 오래 걸리는 NFA의 문제점은 NFA를 DFA로 변환하여 처리함으로 해결할 수 있는데, 이 NFA -> DFA의 변환은 다음 포스팅에서 알아보겠다.