[계산이론] #01. Introduction

Automata란?

톨게이트를 하나 설계한다고 합시다. 자동차가 톨게이트에 도착하면 게이트가 닫치고 운전자가 25센트를 지불하면 게이트가 열리는데요, 이 때 운전자는 5센트, 10센트, 25센트를 선택해서 낼 수 있으며 거스름돈은 반환되지 않는다고 합시다.

이 톨게이트를 만들기 위해 6개의 State가 있는 Machine을 하나 사용할겁니다.

Toll Gate

이 Machine은 6개의 State, $q_0, q_1, ..., q_5$가 존재합니다. 시작은 항상 $q_0$이고 동전을 하나 입력받을 때 마다 State가 바뀌며 입력받은 동전의 종류에 의해 어느 State로 이동하는지가 결정됩니다. 동전을 받다가 $q_5$에 도달하면 게이트가 열린다고 생각하면 되겠죠. 그래서 $q_5$에는 동그라미 2개로 특별하게 표시되어 있습니다.

이런 식으로 만들어진 Machine을 Finite Automaton이라고 하고, 이렇게 이 Finite Automaton이 어떻게 동작하는지를 나타낸 위와 같은 그림을 State Diagram이라고 합니다.

조금 더 간단한 Finite Automaton의 State Diagram

Finite Automaton의 개념 이해를 위해 톨게이트라는 조금 복잡한 예시를 들었었는데, 위처럼 조금 더 간단한 예시로 좀 더 설명을 이어보겠습니다. 지금 보시면 빈 화살표가 $q_1$을 가르키고 있는데, 이건 이 Machine의 시작점이 $q_1$임을 의미합니다. 우리는 이 때 $q_1$을 Start State라고 합니다. 또한, 아까와 같이 $q_2$에 동그라미 2개 표시가 있는데, 이런 상태를 Accept State라고 합니다.

이 Machine에 "1101"이라는 Input이 주어졌다고 생각해봅시다.

$q_1$에서 시작해서 첫 문자가 1이므로 화살표를 따라 $q_2$로 이동합니다. 다음 문자는 1인데, $q_2$에서 시작해 1이라고 적혀있는 화살표를 따라가면 그대로 $q_2$이고, 그 다음은 0이므로 $q_3$로, 그 다음은 1이므로 다시 $q_2$로 이동하게 됩니다.

따라서 이 Finite Automaton에 1101을 입력하게 되면 이 Machine은 $q_2$인 상태에 있게 됩니다. 그리고 이 $q_2$는 Accpet State이기 때문에, 우리는 "이 Machine은 1101을 Accept한다"고 적을 수 있습니다.

 

Deterministic Finite Automata (DFA)

이제 이런 식의 Finite Automaton을 조금 더 수학적인 표현으로 바꿔보겠습니다. 

$$M=\left ( Q, \Sigma ,\delta ,q,F \right )$$

Finite Automaton은 5-tuple인 $M$으로 표현할 수 있는데요, 하나하나 자세히 알아보도록 하겠습니다.

• $Q$는 유한집합으로, 이 Machine에 존재하는 모든 State의 집합입니다.
• $\Sigma$는 Alphabet이라고 불리는 유한집합으로, 이 Machine이 한 턴에 입력받을 수 있는 모든 문자의 집합입니다. 이 집합의 원소를 우리는 Sybmols라고 부릅니다.
• $\delta$는 Transition Function이라고 불리는 $Q\times \Sigma\to Q$ 함수로, 현재 State와 입력받은 Symbol을 입력받아 다음 State를 출력하는 함수입니다.
• $q$는 $Q$의 원소 중 Start State인 것을 위미합니다.
• $F$는 $Q$의 부분집합으로, 모든 Accept State를 원소로 가집니다.

 

이렇게 하나하나 보면 조금 이해하기 어려울 수 있는데, 예시와 위의 정의를 번갈아가며 보시면서 이해해보시면 좋을 듯 합니다.

아까 봤던 Finite Automaton의 State Diagram

방금 나왔던 Finite Automaton입니다. 이 Machine을 수학적 표현으로 바꿔보겠습니다.

• $Q=\left\{q_1, q_2, q_3 \right\}$
• $\Sigma =\left\{0, 1 \right\} $
• $q=q_1$
• $F=\left\{q_2 \right\}$
• $\delta$는 아래의 표로 나타낼 수 있습니다.

위 Finite Automaton의 Transition Function

 

Language

이렇게 Finite Automaton $M$이 있을 때, $L\left(M\right)$을 정의할 수 있습니다. 이는 $M$의 Language라고 불리며, $M$이 Accept하는 모든 문자열의 집합을 의미합니다. 아까 문자열 "1101"을 위 Machine이 Accept 했으므로, 이 내용을 해당 표현으로 바꿔보면 아래와 같겠죠.

$$1101\in L\left(M\right)$$

Finite Automaton $M$에 대하여, $M$이 Accept하는 모든 문자열을 포함하는 집합을 Language $L\left(M\right)$라고 정의하며, 이는 $M$에 의해 Accepted된다고 표현합니다.

그리고, Language $A$에 대해, $A=L\left(M\right)$을 만족하는 Automaton $M$이 존재할 경우 이 Langauge $A$를 Regular하다고 말합니다.

 

Extended Transition Function

아까 봤던 Finite Automaton의 State Diagram

다시 이 Finite Automaton을 보겠습니다. 이 Machine에서의 Transition Function $\delta$에 대해, 이 함수를 확장하여 $\bar{\delta }$를 정의할 수 있습니다.

일반적인 $\delta$가 $\delta (q_2, 0)=q_3,\; \delta (q_2, 1)=q_2$ 같은 식으로 State 하나와 Alphabet 하나를 받아 그 다음 State를 출력하는 함수였다면, $\bar{\delta }$는 하나의 Alphabet뿐만 아니라 문자열에 대해서도 적용 가능하게끔 확장된 형태입니다. 예를 들어, $\bar{\delta }\left ( q_2, 010 \right ) =q_3$와 같은 식입니다. ($q_2$ State에서 0, 1, 0을 연달아 입력하면 $q_3$가 되므로)

이 표현을 사용하면, $L\left(M\right)$을 아래와 같이 정의할 수도 있습니다.

$$L\left ( M \right )=\left\{w:\bar{\delta }\left ( q, w \right )\in F \right\}$$

Start State에서 문자열 $w$를 입력했더니 나온 State가 Accepted State라면, $w$는 $L\left ( M \right )$의 원소라는 뜻입니다.

 

마무리

이번 글에서는 Automata가 무엇인지, 그리고 이 Automata를 수학적 표현으로 어떻게 나타낼 수 있는지에 대해 간단히 알아보았습니다. 다음 글에서는 이 Finite Automata에 대해서 더 자세히 알아보도록 하겠습니다.

감사합니다.

---

이 글은 컴퓨터공학과 학부생이 개인 공부 목적으로 작성한 글이므로, 부정확하거나 틀린 내용이 있을 수 있으니 참고용으로만 봐주시면 좋겠습니다. 레퍼런스 및 글에 대한 기본적인 정보는 이 글을 참고해 주세요.