[Automata Theory] Deterministic Finite Automata

What is Deterministic Finite Automata?

결정 유한 오토마타(Deterministic Finite Automata, 일명 DFA)는 가장 간단한 버전의 컴퓨터라고 할 수 있다. 비록 메모리가 없어 값들을 기억하진 못하지만 기계 내부에 상태가 있고, 값을 읽을 수 있으며, 상태 또한 전이가 가능하다. 실제 이런 기계는 존재하지는 않지만 존재한다면 아래의 그림과 비슷할 것이다.

 

기계는 테이프에 적혀있는 알파벳을 읽게 되는데, 가장 왼쪽부터 읽어가며 한칸씩 오른쪽으로 움직인다. 동시에 기계의 상태는 계속 바뀐다. 실제 컴퓨터도 instruction을 차례로 읽으면서 수행하고, 내부의 상태(register, memory, etc.)를 바꿔간다는 것을 생각해볼 때, 정말 컴퓨터와 비슷하게 느껴진다. 이제 DFA를 엄밀하게 정의해보자.

Definition

DFA $M$은 5가지의 구성 요소가 있어 $\boldsymbol{M=(Q, \Sigma, \delta, q_0, F)}$이다. 이때 각 요소들은

 

1. $Q$ : 상태 집합 (유한집합)
2. $\Sigma$ : 알파벳
3. $\delta: Q\times \Sigma\rightarrow Q$ : 전이함수
4. $q_0 \in Q$ : 초기 상태
5. $F\subseteq Q$ : 최종 상태의 집합

이다. 

 

설명의 편의를 위해 $\delta$를 조금 확장한 함수 $\delta^*: Q\times \Sigma^*\rightarrow Q$를 정의해보자.

 

1. $\delta^*(q, \epsilon) = \delta(q, \epsilon)$
2. $w\in \Sigma^*, a\in \Sigma$에 대해 $\delta^*(q, wa) = \delta(\delta^*(q, w), a)$

정의에 의해 DFA는 $\delta$에 의해 상태가 계속 변화한다. 초기에는 $q_0$, $a\in\Sigma$를 읽었다면 다음 상태는 $\delta(q_0, a)$인 것이다. 이렇게 스트링을 모두 읽게 되면 기계는 멈추고 기계가 가졌던 최종 상태가 $F$에 속하는지 판별한다. 스트링 $w$를 읽었을 때 최종 상태가 $F$에 속한다면 DFA $M$이 $w$를 받아들인다고 한다. 따라서 DFA $M$이 주어지면 받아들여지는 스트링과 받아들여지지 않는 스트링으로 나뉘게 되는데, 이때 $L(M)$을 $M$에 의해 받아들여지는 스트링의 집합으로 정의한다. 이를 엄밀하게 표현하면 아래와 같다.

 

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

 

그리고 당연하게도 $L(M)\subseteq \Sigma^*$은 $\Sigma$로 이루어진 언어이다. 즉, DFA는 이전에 나왔던 Regular Expression과 같이 언어를 표현하는 방식인 것이다.

Example

위의 정의를 처음 본다면 바로 이해가 되지 않을 수 있다. 다음 예를 한번 살펴보자.

위 DFA는 정의대로 말하면 $M=(\{q_0, q_1\}, \{0,1\}, \delta, q_0, \{q_1\})$, $\delta(q_0, 0) = q_1, \delta(q_0, 1) = q_0, \delta(q_1, 0) = q_0, \delta(q_1, 1) = q_1$이다. 원 2개로 표현되는 상태는 최종 상태임을 의미하고 $q_0$에 붙어있는 화살표는 $q_0$가 초기 상태임을 의미한다. 그림을 보면 쉽게 DFA가 어떻게 동작하는지 알 수 있을 것이다. 마치 Logic Design에서 사용하는 FSM(Finite State Machine)과 비슷하고, 실제로 output의 유무 정도만 차이가 있다.

 

그렇다면 이 DFA가 만드는 언어 $L(M)$은 무엇일까? 조금만 생각해보면 어떤 스트링에 0이 짝수개 있으면 $q_0$에서 기계가 멈추게 되어 받아들여지지 않지만 홀수개 있으면 $q_1$에서 기계가 멈추게 되어 받아들여진다. 따라서 $L(M)=\{w:w\in \{0, 1\}^*, w\text{ has odd }0\}$이다. 그렇다면 조금 더 나아가서, 정규표현식으로도 같은 언어를 만들 수 있을까? 한번 생각해보길 바란다.

 

 

 

* 이 글은 서울대학교 박근수 교수님의 '오토마타이론' 강의자료에 기반을 두고 있고, 교수님의 허락을 받고 포스팅을 진행함을 밝힌다.