유한 오토마타 (Finite Automata)

결정적 유한 오토마타 (Deterministic Finite Automata)

결정적 유한 오토마타는 저장 기능이 없는 오토마타입니다.

 

DFA의 정의는 다음과 같습니다.

 

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

여기서 Q는 유한개의 상태의 집합입니다. ∑는 유한개의 입력 기호의 집합이고, δ는 Q X ∑ → Q 의 전이 함수입니다.

q0의 위치에 시작 상태가 들어가고, F에 최종 상태가 들어갑니다. 이때, F는 여러 개일 수 있습니다.

 

DFA는 위 정의에 의해 초기상태인 Q0에서 시작하여, 입력 스트링의 가장 왼쪽에 위치한 입력 포인터가 오토마타의 전이에 의해 하나 왼쪽으로 전진하며 소비합니다. 입력 스트링이 모두 소비되고, 오토마타가 F에 있을 경우, 해당 스트링은 오토마타에 의해 승인된 스트링이고, 아닐 경우, 거부당한 스트링입니다.

 

ex) M = ({q0, q1, q2,}, {0, 1}, δ, q0, {q1}).

이때, δ는 다음으로 정의

δ(q0, 0) = q0, δ(q0, 1) = q1, δ(q1, 0) = 0, δ(q1, 1) = q2, δ(q2, 0) = q2, δ(q2, 1) = q1

 

문법에서 사용했던 ⇒*를 똑같이 적용하여 δ* 를 통해 축약(확장) 가능합니다.

ex) δ*(q0, ab) = q2 == (δ(q0, a) = q1 && δ(q1, b) = q2)

 

오토마타에 의해 승인된 언어는 DFA M에 의해 인식되는 언어 L(M)으로 정의됩니다.

언어는 집합이므로, 해당 언어의 역은 DFA M에 의해 거부되는 스트링들의 집합입니다.

 

언어 중 DFA에 의해서 인식되는 언어를 정규 언어(Regular Languages) 라고 부릅니다. (L = L(M))

 

비결정적 유한 오토마타 (Nondeterministic Finite Automata)

NFA의 경우 DFA와 다르게, 전이 함수에서 다음 상태가 정의되지 않거나, 유일한 상태가 아닐 수 있습니다.

( δ : Q X (∑ ∪ {λ}) → 2^Q)

ex) δ(q0, a, (q1, q2)) 이 경우, 입력 스트링 a를 소비하여 q1, q2 두 상태로 전이 될 수 있음.

δ(q0, λ, q1) 이 경우, 입력 스트링을 소비하지 않고 q1 상태로 전이될 수 있음.

 

NFA의 경우 주어진 스트링에 대해, 전이 함수를 통하여 최종 상태에 도달하는 경우가 한 개 이상 존재하면 받아들여 집니다. 반대로, 거부 되는 경우는 모든 경우의 수를 테스트 했을 때, 최종 상태에 도달하는 경우가 한 개도 존재하지 않는다면 거부됩니다.

 

이때, 다음 상태가 여러개인 전이 함수 라면, 어떤 것을 선택해야 승인되는지 선택하기 전까지 알 수 없기 때문에 선택에 대한 문제가 발생할 수 있습니다.

 

DFA와 NFA의 동등

두 오토마타 M1과 M2가 동등한 경우, 두 오토마타가 인식하는 스트링들이 동등합니다.

 

모든 DFA는 NFA의 한 부류로 전부 NFA에 해당됩니다. 단, 이때 저 명제는 역이 성립하지 않습니다.

또한, 한 언어가 NFA에서 승인된다면, 해당되는 DFA또한 존재합니다.

 

즉, 한 NFA에 대해 그와 동등한 DFA로 변환할 수 있는 알고리즘이 존재합니다.

NFA를 DFA로 변환하는 대표적인 알고리즘 중 하나로  NFA에서 상태들의 집합을 하나의 상태로서 처리하여 결정적으로 만들어 주는 방법이 있습니다. 

ex) δ(q0, a, (q1, q2)) 와 같이 q0에서 a를 소비하면 (q1, q2)라는 상태로 전이하게 해서 다음 상태가 유일하게 해줍니다.

 

이를 위해, 변환 테이블을 사용하여 정리합니다.