결정적 유한 오토마타(DFA), 비결정적 유한 오토마타(NFA)

결정적 유한 오토마타 (DFA)

DFA는 다음 두 가지 조건을 만족해야 함

1. ε에 의한 상태 전이가 없고

2. δ(q,a) = {P1, P2, ..., Pn}에서 n = 1 이다

즉, δ : Q x Σ -> Q

하나의 입력 기호에 대해 다음 상태는 오직 하나이거나 상태 전이가 없어야 함

 

ε에 의한 상태 전이를 ε-전이라고도 함

 

ex.

0과 1이 짝수 개인 문자열을 받아들이는 유한 오토마타가 DFA인지 알아보고 상태 전이도로 표현

M = ( Q, Σ, δ, q0, F )

Q = {q0, q1, q2, q3}

Σ = {0, 1}

q0 = q0

F = {q0}

 

상태전이도

 

δ	0	1
q0	q2	q1
q1	q3	q0
q2	q0	q3
q3	q1	q2

상태전이표

 

 

그런데 이 방식은 한 문자 한 문자 받아들여서, 전체 문자열이 한 번에 어디로 가는지 알기 힘듦

그래서 확장

Q x Σ -> Q => Q x Σ* -> Q

확장된 전이 함수는 한 개의 기호를 문자열로 확장함

 

δ(q0, ε) = q0

δ(q0, wa) = δ( δ(q0, w), a )

 

여기서 w ∈ Σ* 이고, a ∈ Σ

즉, q0 상태에서의 문자열 wa

-> w를 전부 본 상태에서 a를 보는 것

 

ex.. (필요 DFA는 있다고 가정)

δ*(q0, a12)

= δ(δ*(q0, a1), 2)

= δ(δ(δ(q0, a), 1), 2)

= δ(δ(q1, 1), 2)

= δ(q1, 2)

= q1 ∈ F

와 같이 인식됨

 

q0 a / q1 1 / q1 2 ...

 

---

 

비결정적 유한 오토마타 (NFA)

1. ε에 의한 상태 전이가 있거나

2. δ(q,a) = {P1, P2, ..., Pn}에서 n >= 2인 n이 하나라도 존재

즉, δ : Q x Σ -> 2^Q

하나의 입력 기호에 대해 다음 상태가 두 개 이상인 것이 하나라도 존재

 

ex. 2개의 연속적인 0이 있거나 2개의 연속적인 1이 있는 문자열

M = ( Q, Σ, δ, q0, F )

Q = {q0, q1, q2, q3, q4} ∅

Σ = {0, 1}

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

q0 = q0

F = {q2, q4}

// q0, q2, q4의 스스로 전이는 필요 없어 보이는데..? 일단 인식이 안되는 건 아님

---

 

NFA로부터 문장 인식하기

 

다음 유한 오토마타가 문장 baabb를 인식하는가

M =(Q, Σ, δ, q0, F) 단, Q = {q0, q1, q2, q3} Σ = {a, b} δ: δ(q0, a) = {q0, q1} δ(q0, b) = {q0} δ(q1, a) = {q2} δ(q2, a) = {q3} q0 = q0 F = {q3}

1. 하나하나 전이함수 적용해서 인식하기

2. 갈 수 있는 상태를 모두 그림으로 표현하여 인식하기

 

1. 하나하나 전이함수 적용해서 인식하기

δ(q0, b) = {q0}

δ(q0, a) = {q0, q1} - q0 선택

δ(q0, a) = {q0, q1} - q0 선택

δ(q0, b) = {q0}

δ(q0, b) = {q0}

- 다 읽은 후 최종 상태는 q0 .. 하지만 최종 상태는 q3이므로 안됐음

- 하지만 아직 적용하지 않은 상태들이 있음. 

δ(q0, b) = {q0}

δ(q0, a) = {q0, q1} - q0 선택

δ(q0, a) = {q0, q1} - q1 선택

δ(q1, b) = {q2}

δ(q2, b) = {q3}

- 이 경우 baabb가 주어진 NFA에 의해 인식됨

 

2. 갈 수 있는 상태를 모두 그림으로 표현하여 인식하기

입력 문자열 baabb를 모두 읽은 후 도달 가능한 상태 -> {q0, q3}

{q0, q3} ∩ F = {q3}

-> baabb는 주어진 NFA에 의해 인식됨

 

DFA처럼 확장 가능

δ : Q × Σ -> 2^Q ⇒ Q × Σ* -> 2^Q
단, δ*(q, ε) = {q}

δ*(q, wa) = {r | δ*(q, w)에 의해서 도달할 수 있는 모든 상태 p에 대해서 r ∈ δ(p, a)}
           = ⋃_{p ∈ δ*(q, w)} δ(p, a)

 

δ(q0, baabb)

= δ(q0, aabb)

= δ(q0, abb) ∪ δ(q1, abb)

= {δ(q0, bb) ∪ δ(q1, bb)}  ∪ ∅    // 왼쪽은 δ(q0, abb)의 결과, 우측은 δ(q1, abb)인데 전이 없으니 전이 없음

= δ(q0, b) ∪ δ(q2, b)

= {q0} ∪ {q3}

= {q0, q3}

{q0, q3} ∩ F = {q3}

-> baabb는 주어진 NFA에 의해 인식된다

 

 

NFA와 DFA

- DFA보다 NFA가 언어의 구조를 쉽게 표현

- NFA는 DFA보다 프로그램으로 구현하기 어려움

- DFA는 NFA보다 프로그램으로 구현했을 경우에 효율면에서 훨씬 우수

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

 

DFA와 NFA는 서로가 동등 (equivalent)