[계산이론] - (2) 유한 오토마타 (Finite Automata) : DFA, NFA

 

유한상태 기계(finite state machine) (유한 오토마타)

유한 인식기는 유한 개수의 상태를 가지며, 그 임시 저장장치가 없기 때문에 유한하다고 하며,

문자열을 처리하면서 이를 승인(accept)하거나 거부(reject)하는 기능을 하기 때문에 인식기(accpter)라 합니다.

따라서 유한 인식기를 간단한 패턴 인식 매커니즘이라 볼 수 있습니다.

 

 

 

 

 

결정적 유한 인식기 (Deterministic finite accepter, DFA)

결정적이라는 단어의 의미는 해당 오토마타가 항상 하나의 선택만을 취할 수 있음을 의미합니다.

DFA는 정규 언어(regular language)라 불리는 특별한 형태의 언어를 정의하기 위해 사용합니다.

 

 

결정적 유한 인식기(Deterministic finite accepter, DFA) M은 다음과 같은 5가지의 원소 쌍으로 정의됩니다.

$$M = (Q, \;\; \Sigma,\;\; \delta ,\;\;q_0,\;\; F)$$

 

각각의 기호는 다음 의미를 가집니다.

Q : 내부 상태(internal state)들의 유한 집합입니다.
Σ : 심벌들의 유한 집합이며, 입력 알파벳(input alphabat)이라 불립니다.
δ : Q X Σ   ->  Q    는 전체 함수(total function)이며, 전이 함수(transition function)라 불립니다.
q(0) : Q에 포함되는 원소이며 초기 상태(initial state)입니다.
F : Q의 부분집합이며, 승인 상태(final state)입니다.

 

 

 

결정적 유한 인식기는 처음에 초기 상태 q(0)에 있는 것으로 가정하며 입력 장치는 입력 문자열의 가장 왼쪽 심벌에 놓여 있습니다.

오토마타가 이동할 때마다 입력 장치는 한 자리씩 오른쪽으로 이동합니다. 즉 입력 문자를 하나씩 읽어냅니다.

입력 문자열의 맨 끝에 도달했을 경우 오토마타가 승인 상태에 있으면 해당 문자열이 승인되고 그렇지 않으면 거부됩니다.

 

하나의 내부 상태로부터 다른 상태로의 전이는 전이 함수 δ에 따라 결정됩니다. 

 

 

 

 

 

 

 

전이 그래프(transition graph)

유한 오토마타를 가시적으로 표현하기 위해서 보통 전이 그래프를 사용합니다.

전이 그래프에서의 정점(Vertex)은 상태(state)를 나타내며, 간선(edge)는 전이(transition)를 나타냅니다.

 

 

정점의 라벨은 상태의 이름이며,

간선의 라벨은 입력 심벌의 현재 값이 됩니다.

 

 

 

예를 들어, q(0)과 q(1)이 어떤 dfa M의 내부 상태들일 경우, M에 대한 그래프에는 라벨 q(0)과 라벨 q(1)을 갖는 정점들이 존재하게 됩니다.

 

초기 상태는 라벨이 붙지 않은 외부로부터 진입하는 간선에 의해 지정되며,

승인 상태는 이중 원(double circle)으로 표시합니다.

 

 

 

예를 들어 다음 dfa를 그려보겠습니다.

 

$$M = (\left\{q_0, q_1, q_2\right\}, \left\{0, 1\right\}, \delta , q_o, \left\{q_1\right\})$$

전이 함수 δ :

 

$$\delta(q_0, 0) = q_o, \;\;\; \delta(q_0, 1) = q_1 $$ 

$$\delta(q_1, 0) = q_o, \;\;\; \delta(q_1, 1) = q_2 $$ 

$$\delta(q_2, 0) = q_2, \;\;\; \delta(q_2, 1) = q_1 $$ 

 

 

 

 

 

 

 

 

 

확장 전이 함수

때로는 전이 함수 대신 확장 전이 함수(extended transition function)를 도입하는 것이 편리한 경우도 있습니다.

 

확장 전이 함수는 다음과 같습니다.

$$\delta^{*}  \;:\; Q \times {\Sigma}^{*} \to Q$$

 

해당 함수의 두 번째 인수는 단일 심벌이 아닌 문자열이며, 함수 값은 오토마타가 주어진 문자열을 모두 읽은 후에 놓이게 되는 상황입니다.

 

 

예를 들어 다음과 같습니다.

 

전이 함수가 아래와 같은 경우

$$\delta(q_0, a) = q1 \;\;\; and \;\;\; \delta(q_1, b) = q2$$

 

다음과 같이 확장 전이 함수를 사용하여 표현이 가능합니다.

$$\delta^{*}(q_0, ab) = q_2$$

 

 

 

 

공식적으로, 모든 q ∈ Q, w ∈ Σ*, a ∈ Σ에 대하여, δ*는 다음과 같이 정의될 수 있습니다.

$$\delta^{*}(q, \lambda) = q$$

$$\delta^{*}(q, wa) = \delta(\delta^{*}(q_o, \lambda), a) = \delta(q_0, a) = q_1$$

 

 

 

 

 

 

 

 

DFA에 의해 인식되는 언어

$$M = (Q, \;\;\; \Sigma, \;\;\;\delta \;\;\;,q_0, \;\;\;F)$$

위 DFA에 의해 인식되는 언어란, M에 의해 승인되는 Σ에 대한 모든 문자열들의 집합입니다.

 

공식적인 표현을 사용하면, 다음과 같습니다

$$L(M) = \begin{Bmatrix}
w \in \Sigma^{*} : \delta^{*}(q_0, w) \in F \end{Bmatrix}$$

 

전이 함수 δ와 확장 전이 함수 δ*가 모두 전체 함수(total function)임을 유의하여야 합니다.

 

각 단계에서 단 하나의 전이만이 정의되며, 따라서 이러한 오토마타를 결정적(deterministic)이라 합니다.

 

dfa는 Σ*의 모든 문자열들을 처리하여 이를 승인하거나 승인하지 않습니다. 

 

승인하지 않는다는 것은 주어진 dfa가 승인 상태가 아닌 다른 상태에서 종료함을 의미하며 따라서 다음이 성립합니다.

$$\overline{L(M)} = \begin{Bmatrix}
w \in \Sigma^{*} : \delta^{*}(q_0, w) \notin  F \end{Bmatrix}$$

 

 

 

 

 

 

 

 

 

 

트랩 상태 (trap state)

어떤 상태에서 다른 상태로 전이한 이후 그 상태를 벗어날 수 없게 되는 상태를 의미하며, 예를 들어 다음과 같습니다.

 

위 전이 그래프를 보면, q1에서 q2 상태로 전이하게 되면, 이후 q2 상태를 벗어날 수 없게 되므로, q2는 트랩 상태(trap state)가 됩니다.

 

 

 

 

 

 

 

 

정규 언어

모든 유한 오토마타는 특정 언어를 인식하게 됩니다.

모든 가능한 유한 오토마타들을 고려해보면 이들과 관련된 언어들의 집합을 얻을 수 있습니다.

이러한 언어들의 집합을 언어군이라 부릅니다.

 

결정정 유한 오토마타(dfa)에 의해 인식되는 언어군은 극히 제한되어 있습니다.

이 언어군에 속하는 언어들의 구조와 성질들을 이후 공부하도록 하고, 우선 이 언어군을 부르는 명칭은 다음과 같습니다.

언어 L에 대하여, L = L(M)을 만족하는 결정적 유한 인식기(dfa) M이 존재하고, 오직 그럴 때에만 L을 정규 언어(regular lanuage)라 부릅니다.

 

 

 

추가로 다음을 참고하시면 정규 언어 이외 다른 언어군을 확인하실 수 있습니다.

[계산이론] - 언어, 문법, 오토마타

촘스키 위계 - 위키백과, 우리 모두의 백과사전

 

 

 

 

 

 

 

 

 

 

 

 

비결정적 유한 인식기 (Nondeterministic finite accepter, NFA)

위에서 공부했던 dfa는 각 상태에서 입력 심벌이 주어질 경우 하나의 전이만이 가능했습니다.

 

이번에는 오토마타가 때에 따라 하나 이상의 전이를 할 수 있는 경우에 대해서 생각해 보도록 하겠습니다.

이러한 오토마타를 비결정적이라고 합니다.

 

 

 

비결정성은 오토마타의 이동에 있어서 선택을 할 수 있음을 의미합니다.

각 상황에서 유일한 이동만을 규정하기보다 가능한 여러 가지 이동들의 집합을 허용하는 것인데,

공식적으로 이는 오토마타의 전이 함수가 상태들의 집합을 치역(range)으로 갖게 함으로써 가능해집니다.

 

 

 

비결정적 유한 인식기(nondeterministic finite accepter) 또는 nfa는 다음과 같은 5가지 원소의 쌍으로 정의됩니다.

$$ M = (Q,\;\;\; \Sigma,\;\;\; \delta,\;\;\; q_0, \;\;\;F)  $$

 

여기서 전이 함수 δ를 제외하고는 결정적 유한 인식기(dfa)와 동일하고, 전이 함수는 다음과 같습니다.

$$\delta : Q \times (\Sigma \cup \begin{Bmatrix}
\lambda \end{Bmatrix}) \to 2^{Q}$$

 

위 nfa의 정의와 dfa의 정의 사이에는 크게 세 가지 차이점이 존재합니다.

 

 

 

 

 

치역이 멱집합

비결정적 인식기에서는 δ의 치역은 Q의 멱집합 2^Q내에 있으며, 따라서 그 값이 Q의 단일 원소가 아닌 Q의 부분집합이 됩니다.

이 부분집합은 해당 전이에 의해 도달할 수 있는 모든 가능한 상태들의 집합이 되는 것입니다.

예를 들어, 만일 현재 상태가 q1이고, 이 상태에서 심벌 a가 읽혀지고, 전이 함수가 다음과 같다면

$$\delta(q_1, a) = \begin{Bmatrix}
q_0, q_2 \end{Bmatrix}$$

q0나 q2가 해당 nfa의 다음 상태가 될 수 있는 것입니다.

 

 

 

 

 

람다 전이(lambda transition)

또한 nfa에서는 전이 함수 δ의 두 번째 인수로 λ를 허용합니다.

이는 nfa가 심벌을 읽지 않고도 상태 전이를 할 수 있음을 의미합니다.

 

 

 

 

 

 

공집합으로의 이동

마지막으로 nfa에서는 집합 δ(q(i), a)가 공집합일 수 있으며, 이런 특정 상황에 대하여 정의된 전이가 없을을 의미합니다.

따라서 nfa에서 δ는 전체 함수(total function)이 아닙니다.

 

dfa에서와 마찬가지로 nfa에서도 전이 함수는 두 번째 인수로 문자열을 갖도록 확장될 수 있습니다. (즉 확장 전이 함수를 가질 수 있습니다.)

 

 

 

또한 dfa에서 처럼 nfa에 의해 인식되는 언어는 다음과 같이 정의됩니다.

 

$$nfa\;\; M =(Q, \;\;\;\Sigma, \;\;\;\delta, \;\;\;q_0, \;\;\;F)$$에 의해 인식되는 언어는 다음과 같습니다:

 

$$L(M) =\left\{{\Sigma}^{*} : \delta^{*}(q_0, w) \cap F \neq  ∅  \right\}$$

 

 

 

 

 

 

 

 

nfa의 예시

$$\delta(q_0, 0) = \left\{ q_1, q_2 \right\} \;\;\; \delta(q_0, 1) = \left\{ q_1, q_2 \right\} $$

$$\delta(q_1, 0) = \left\{ q_0, q_2 \right\} \;\;\; \delta(q_0, 1) = \left\{ q_1, q_2 \right\} $$

$$\delta(q_1, \lambda) = \left\{ q_1 ,q_2 \right\} $$

$$\delta(q_2, 0) = \varnothing   \;\;\; \delta(q_2, 1) = \left\{ q_1, q_2 \right\} $$

 

 

 

 

 

 

확장 전이 함수

dfa에서와 마찬가지로 nfa에서도 전이 함수는 두 번째 인수로 문자열을 갖도록 확장될 수 있습니다.

확장 전이 함수는 다음과 같이 정의됩니다.

 

전이 그래프에서 qi로부터 qj로의 라벨 w를 갖는 보행이 존재하고, 오직 그럴 때에만

$$\delta^{*}(q_i, w)$$가 qj를 포함합니다.

이는 모든 $$q_j \in Q, \;\; w \in {\Sigma}^{*}$$에 대해 성립합니다.

 

이때 Q는 오토마타가 상태 qi에서 시작하여 입력 문자열 w를 읽은 후에 놓여질 수 있는 상태들의 집합입니다.

 

 

 

 

 

 

 

 

nfa에 의해 인식되는 언어

다음과 같이 정의됩니다.

$$L(M) = \left\{ w \in {\Sigma}^{*} \;:\; \delta^{*}(q_0, w) \cap F \neq \varnothing   \right\}$$

전이 그래프의 초기 정점에서 승인 정점까지, 라벨이 w인 보행이 존재하는 모든 문자열 w 로 구성됩니다.

 

 

 

 

 

 

 

 

종말 형상(dead configuration)

특정한 상태에서 이동할 상태가 없는 경우,

즉 이동이 정의되지 않아 스트링이 남아있음에도 불구하고 전이가 불가능한 형상을 종말 형상이라 합니다.

 

추가로 dead state는 final state로 전이될 수 없는 state입니다.