[오토마타] 1. 유한 결정적 오토마타(DFA, Deterministic Finite Automata)

• 컴퓨터란 무엇인가?
• 컴퓨터는 무엇을 할 수 있고, 무엇을 할 수 없는가?
• 컴퓨터가 연산하기 쉬운 문제와 어려운 문제의 차이는 무엇인가?

 

위 질문들은 컴퓨터 과학의 가장 근본적인 질문들이다. 연산 이론(computational theory)은 위 질문들을 고민하는 전산학의 한 꼭지다. 이 질문들이 어려운 이유는 현대의 컴퓨터는 수학적으로 정의하기 너무나도 복잡한 기계장치이기 때문이다. 컴퓨터란 무엇일까? 컴퓨터의 특징을 생각해보자.

 

• 컴퓨터의 메모리는 유한하다. 즉 메모리가 표현할 수 있는 상태들도 유한하다.
• 컴퓨터의 연산 결과 또한 유한한 메모리로 표현가능하다.
• 컴퓨터는 연산을 수행하는 장치이다. 그러나 컴퓨터는 입력이 들어오기 전까지, 다음에 자신이 수행해야 할 연산에 대해 알 수 없다.
• 컴퓨터는 몇 가지 기본 연산을 가지고, 복잡한 연산을 수행한다.

 

이 컴퓨터의 특징들을 공유하는 수학적인 모델, 유한 오토마타(Finite Automation)를 소개한다. 그 전에, 오토마타의 정의에 필요한 기본적인 개념들부터 소개한다.

---

알파벳, 문자열, 언어

• 알파벳(Alphabet): 유한하고 비어있지 않은 문자들의 집합. Σ로 표기한다.

• 문자열(String): 알파벳들의 유한히 나열한것(finite sequence). 나열된 알파벳의 개수는 길이(Length)라고 부른다.
  • 길이가 0인 문자열은 ε로 표기한다.
  • $ \Sigma^{i} $는 길이가 i인 문자열의 집합을 의미한다.
  • $ \Sigma^{*} $는 주어진 알파벳으로 만들 수 있는 모든 문자열의 집합을 의미한다.

• 언어(Language): 주어진 알파벳 Σ 위의 우리가 관심있는 문자열들의 집합이다. $ \Sigma^{*} $의 부분집합이다. 

만약 우리가 어떤 언어 L를 "주어진 알파벳 Σ={0,1} 위에서, 0과 1의 개수가 같은 문자열들의 집합" 이라고 정의한다면, '0110'은 L의 원소이지만, '111'은 아닐 것이다. 우리는 0110에 대해서는 True(=1)를, 111에 대해서는 False(=0)을 반환하는 함수 f가 필요하다. 함수 f는 어떤 문자열 x가 주어지면, 그 x가 L의 원소인지 아닌지 판단하는 일종의 membership test다. 수학적으로 표현하면 아래와 같다. 

 

---

유한 오토마타

Figure 1. transition diagram

위의 transition diagram을 살펴보자. 동그라미 안의 $q_1,q_2$는 상태(states)라고 부른다. 상태가 2개 혹은 유한개 있는 이 오토마타는 유한 오토마타(Finite Automata)라고 부른다. 어떤 문자열이 이 오토마타에 입력되면, 이 오토마타는 해당 문자열이 우리가 원하는 언어 A에 속하는지 아닌지 판단하는 역할을 한다.

 

예를 들어, "0011"이 입력 됐다고 하자. 화살표가 시작되는 $q_1$을 시작 상태(start state)라고 부른다. $q_1$ 부터 시작하여, 문자열의 앞글자씩 확인하며 $q_1 \to q_1 \to q_2 \to q_2$ 로 상태가 전환된다. 다이어그램의 $q_2$ 동그라미는 테두리가 두 겹으로 되어 있는데, 이것을 최종 상태(final state)라고 부른다. 문자열 "0011"은 최종상태 $q_2$를 마지막으로 도착하였기에 "0011"은 우리가 원하는 언어다. 하지만 "010"은 $q_1$에서 멈추기에, 언어가 아니다. 우리는 이것을 이렇게 표현한다.

직관적으로, 우리는 위 오토마타가 수용(accept)하는 언어는 "1로 끝나는 문자열"임을 이해할 수 있다. 어떤 문자열이 0으로 끝나면 $q_1$에서 연산이 종료될 것이기 때문이다. 이렇게 유한 오토마타로 표현할수 있는 언어는 정규 언어(regular language)라고 부른다. 언어가 유한 오토마타로 표현되는 정규언어인지 아닌지 판단하는 방법에 대해서는 나중에 다룬다. 언어 A = {1로 끝나는 모든 문자열}은 정규 언어다. 복잡해보이는 다이어그램을 "1로 끝나는 문자열"로 특징을 뽑아내는 것을 characterize한다고 부른다.

 

아래와 같은 표현도 사용한다. 이때 L(M)은 M에 의해 수용되는 모든 문자열들의 집합이다.

---

엄격한 정의

M은 5개의 요소로 정의된다.

• Q는 가능한 모든 상태들의 집합이다.
• Σ는 가능한 알파벳이다.
• δ는 현재 상태와 알파벳을 입력으로 받아 다음 상태를 출력하는 전이 함수다.
• $q_0$는 시작 상태(start state)를 의미한다.
• F는 가능한 최종 상태(final state)의 집합을 의미한다. 공집합도 가능하다.

그리고 "Deterministic"이라는 단어는 하나의 상태, 하나의 알파벳이 주어졌을때 가능한 다음 상태는 오직 하나임을 말한다. 다음 상태가 두 개 이상이거나 없는 경우는 "Nondeterministic"으로 구분된다.

 

δ 전이 함수를 정의하는 방법이 고민일 수 있다. 첫번째 방법은 앞서 소개한 transition diagram을 이용하는 것이다. 두번째 방법은 transition table을 이용하는 것이다. Figure 2와 같은 형태다. $\to$ 기호는 그 상태가 시작 상태임을, * 기호는 그 상태가 최종 상태임을 표현한다. Diagram을 이용하던, table을 이용하던 우리가 지금 다루는 DFA는 "Deterministic" 하기 때문에, 모든 상태와 모든 입력 알파벳에 대해서 더도말고 덜도말고 딱 하나의 다음 상태가 반드시 존재해야 한다.

Figure 2. transition table

 

δ 전이함수는 입력으로 알파벳을 받는다. 즉, 지금으로써는 110이 오토마타에 입력되었을 때, 출력되는 오토마타의 상태를 수학적으로 표현하려면, $\delta(\delta(\delta(q_0, 110)))$ 처럼 복잡하게 표현해야 한다. 확장된 전이함수(extended transition function)을 이용해서, $\hat{\delta}(q_0, 110)$ 처럼 간단히 표현할 수 있다. 수학적으로 표현하면 아래와 같다.

이 $\hat{\delta}$를 이용해서, 어떤 DFA M이 인식하는 언어 A를 아래처럼 담백하게 다시 정의할 수 있다.