Finite Automata

개요

Finite Automaton^[1]은 유한한 메모리를 가진 단순한 계산 장치를 수학적으로 모델링한 것이며, FSM(Finite State Machine)의 가장 기본적인 형태이다. 이는 단순한 계산 장치이며, "유한 메모리"이기 때문에 무한한 기억이나 복잡한 연산이 불가능하고, 오직 현재 상태와 입력에 따라 동작만 결정된다는 특징이 있지만, 다양한 활용 분야를 가지고 있다. 예를 들어 자판기, 엘리베이터, 가전제품과 같은 단순 동작 장치들은 모두 finite automata로 모델링될 수 있다. 이들은 현재 상태(예: 금액 투입 상태, 층 수, 전원 상태)에 따라 행동을 정한다. 또한 텍스트 에디터, 스팸 필터, 검색 엔진, 컴파일러 등은 문자열 패턴 매칭 문제를 해결하기 위해 해당 원리를 사용한다. 중요한 것은 모든 실제 컴퓨터도 유한한 메모리를 가지므로, 이론적으로는 finite automaton이라고 볼 수 있다.

Finite Automata as Language Recognizers

Finite automata는 문자열(언어)을 인식하는 기계로 이해할 수 있으며, 이는 아래와 같은 구성 요소로 이뤄 진다:

Finite Control: 현재 내부 상태를 저장하는 장치.
Input Tape: 기계에 주어지는 입력 문자열이 있는 테이프.
Read Head: 입력 테이프에서 현재 어떤 위치(문자)를 읽고 있는지 가리키는 지시자.

이러한 finite automata는 아래와 같은 단계를 거쳐 작동한다:

문자열을 왼쪽에서 오른쪽으로 차례대로 한 글자씩 읽음.
각 단계에서 finite control이 현재 상태와 입력 문자에 따라 "다음 상태"를 결정.
입력 문자열 끝까지 다 읽으면, current state에 따라 문자열을 수용(accepted) 또는 거부(rejected).

이때 어떤 finite automaton이 수용하는 모든 문자열 집합을 그 automaton이 인식(recognize)하는 언어라고 부른다.

State Diagrams

Finite automata는 상태 다이어그램(state diagram) 으로 시각적으로 표현할 수 있다. 이는 figure 1과 같이 표현된다. Figure 1에 나타난 예시 상태 다이어 그램을 해석하면 아래와 같다.

Q1: 시작 상태, 입력 0이 들어오면 Q1에 머무름, 1이 들어오면 Q2로 이동.
Q2: 수용 상태, 입력 1이면 Q2에 머무르고, 0이면 Q3으로 이동.
Q3: 수용 상태 아님, 입력(0,1) 모두 다시 Q2로 돌아감.

즉, 해당 finite automata는 마지막 입력이 1, 혹은 0이 문자열 끝에 짝수개 만큼 있으면 해당 문자열을 수용한다.

Formal Definition of Finite Automaton

DFA(Deterministic Finite Automaton)은 아래와 같은 5-튜플([math]\displaystyle{ Q, \Sigma, \delta, q_0, F }[/math])로 정의할 수 있다:

[math]\displaystyle{ Q }[/math]: 유한 상태 집합
[math]\displaystyle{ \Sigma }[/math]: 유한 입력 기호 집합
[math]\displaystyle{ \delta }[/math]: [math]\displaystyle{ Q\times \Sigma \rightarrow Q }[/math]: 전이 함수(transition function), 현재 상태와 입력 기호를 다음 상태로 매핑
- [math]\displaystyle{ Q\times \Sigma }[/math]는 상탱 집합과 알파벳 집합의 모든 가능한 쌍이며, 전이 함수 [math]\displaystyle{ \delta }[/math]는 이 쌍을 받아서 새로운 상태로 매핑하는 역할을 한다. 이때 전이 함수는 모든 (state, input) 쌍에 대해 하나의 출력만 존재해야 한다. 따라서 결정적(deterministic)이라고 한다.
[math]\displaystyle{ q_0 \in Q }[/math]: 시작 상태(start state)
[math]\displaystyle{ F \subseteq Q }[/math]: 수용 상태 집합(accept states)

이를 통해서 DFA M이 수용하는 어떤 문자열 집합 [math]\displaystyle{ w = w_1w_2\cdots w_n }[/math]일 때, [math]\displaystyle{ M = (Q, \Sigma, \delta, q_0, F) }[/math]이 [math]\displaystyle{ w }[/math]를 "수용"한다는 것은 아래와 같이 정의된다.

어떤 순열 [math]\displaystyle{ r_0r_1r_2\cdots r_n }[/math]이 존재하여 아래의 조건을 만족한다.
1. 시작 상태: [math]\displaystyle{ r_0 = q_0 }[/math]
2. 각 단계에서 [math]\displaystyle{ \delta(r_i, w_{i+1}) = r_{i+1}, i = 0,1,\cdots,n-1 }[/math] 
3. [math]\displaystyle{ r_n \in F }[/math]: 문자열을 다 읽은 뒤 마지막 상태 [math]\displaystyle{ r_n }[/math]이 수용 상태 집합에 포함

이를 바탕으로 위 조건을 만족하는 문자열 [math]\displaystyle{ w }[/math]들의 집합을 M이 인식하는 언어(language recognized by M) 라고 부르며, 이는 아래와 같다:

[math]\displaystyle{ L(M) = \{w\in \Sigma^*|M\,\, accepts\,\, w\} }[/math]

Other Ways to Model Computing Devices

유한 오토마타를 언어 인식기(language recognizer)로만 인식할 수 있는 것은 아니며, 아래와 같이 간주할 수 있다:

Language generators: 입력을 소비(consuming)하는 대신 기호를 생성(emitting)하는 모델.
Transducers: 기호를 읽으면서 동시에 다른 기호를 출력.
Interactive: 환경과 상호작용(interaction)하면서 동작하는 오토마타.

각주

↑ 단수형이 automaton, 복수형이 automata이다.

[1] 단수형이 automaton, 복수형이 automata이다.

[1]