유한 오토마타 -결정적 유한 인식기(dfa)

결정적 유한 인식기, 줄여서 dfa는 유한개의 상태를 가지고 있는 오토마타다. 

dfa는 다음과 같이 정의 될 수 있다.

$$M=(Q,\Sigma,δ,q_0,F)$$

Q는 내부 상태, 즉 그래프로 치면 노드에 해당하고, ∑는 심벌들의 유한집합, 즉 방향 그래프의 간선에 해당한다. 또한 δ는 전이 함수이고, q_0은 처음 시작하는 지점, 즉 입력을 받는 지점을 나타낸다. F는 승인상태들의 집합이다. 승인상태는 이중 원으로 표시한다.

 

전이함수는 다음과 같이 표기한다.

$$\delta(q_0,a)=q_1$$

상태 q_0에 a가 입렵될 시 q_1상태로 전이 한다는 뜻이다. 이를 가시적으로 표현하기 위해 보통 전이 그래프를 사용해서 표시한다.

 

확장 전이함수를 사용해 함수를 나타내는 경우도 있다.

$$\delta(q_0,a)=q_1 , \delta(q_1,b)=q_2 이면 ,  \delta^*(q_0,ab)=q_2가 성립한다.$$

 

이것에 대한 정의는 다음과 같다.

$$\delta(q_0,a)=\delta(\delta^*(q_0,a),b)$$가 성립한다.

 

언어란 분명하게 주어진 오토마타에 의해 승인되는 모든 문자열들의 집합을 말한다. 이런 언어를 정규 언어라 한다.  따라서 아래의 표현이 성립된다.

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

이 표현을 읽으면 입력문자열인 w는 심벌들의 유한집합에 포함되고, δ^*(q_0,w)는 승인상태에 포합된다 라고 읽을 수 있다. 

 

트랩상태란 오토마타 그래프에서 더이상 어느 상태로 이동 할 수 없는 상태를 말한다.

q_2상태로 가면 어떤 문자를 입력하더라도 다른 상태로 갈 수 없고, 승인 상태가 될 수도 없다. 이때 q_2를 트랩상태라 한다.

또한 dfa의 특징으로는 한 상태에 대해 심벌에 대해 하나의 간선만 존재 할 수 있다는 것이다.

무슨 소리인가 하면, 위 사진을 보면 한 상태에서 각기 다른 심벌의 간선은 존재 가능하지만, 오른쪽 처럼, 하나의 상태에서 같은 심벌의 간선이 복수 존재할 수 없다는 것이다.

 

dfa를 그래프로 잘 그리는 방법은 그저 많이 해보는 방법밖에 없다고 생각한다. 알고리즘이라고 생각하면 편하다. 답은 정해진게 없지만, 결과는 정해져 있기에. 알고리즘도 공식이 없지 않는가. 그와 마찬가지로 dfa를 그래프로 그리는것 또한 공식따윈 없다.