[오토마타 이론] 유한 오토마타 기본 (언어, DFA & NFA)

이번에 ReDoS 관련 발표를 준비하면서 깨달은 거지만 유한 오토마타에 대한 기본 개념을 배웠었다.. FSM(finite-state machine)이란 이름으로 말이다. 아예 까먹고 있다가 기억나서 다시 공부해본 김에 잊어버리기 전에 정리해두기로 했다.

 

Automata = 이산 시간동안 주어진 입력에 의존해 작동하는 수학적인 기계

유한 오토마타 정의

오토마타라는 단어가 '자동'을 뜻하는 그리스어에서 왔다고 하는 데, 오토마타는 미리 정해진 명령에 의해 자동으로 반응하는 계산 능력을 지닌 기계장치를 추상화한 것 정도로 생각하면 된다. 오토마타는 물리적으로 존재할 수도 있고 존재하지 않아도 된다.

그 중에서 유한 오토마타는 이름에서 알 수 있듯 finite하다. 즉, 유한한 개수의 상태를 가진 오토마타를 지칭한다.

여기서 뒤늦게 깨달았다. '유한 상태라. 어디서 배웠는데,,?'

유한 오토마타를 해석해서 유한 상태 기계(FSM)이란 이름으로도 부를 수 있다.

일단 유한 오토마타 개념은 이쯤 잡아두고, 언어에 대해서 먼저 살펴본 후에 더 설명을 이어가도록 하겠다.

 

Language: The set theory of strings

형식 언어

우리가 사용하는 언어는 자연어(Natural Language)이다. 이 자연어를 완벽하게 처리할 수 있는 것은 인간의 뇌밖에 없다.(현재 인공지능 분야에서 자연어를 기계가 처리할 수 있게 하기 위해 노력하는 중이다.) 따라서 인간이 사용하는 자연어를 기계가 알아 듣게 하려면 기계가 사용하는 언어로 바꿔 주어야 한다. 기계가 알아 듣는 언어는 형식 언어로, 형식 언어는 언어의 문법 구조를 수학적으로 보편적인 형식으로 만든 인공 언어이다.

촘스키가 제시한 형식 언어의 계층 구조

 

그럼 형식 언어의 요소들을 하나씩 살펴보자.

1) Symbol

심볼은 어떠한 언어를 구성하는 가장 작은, 기본적인 단위의 기호이다. 자연어로 예를 들자면, 'a', 'b', 'c', 'd' 등이 각각 심볼이다.

 

2) Alphabet ∑

알파벳은 심볼들로 구성된 유한 집합이다.

도식화해서 나타내자면, ∑ = {symbol1, symbol2, ...} 가 될 것이다.

마찬가지로 자연어로는 {'a', 'b', 'c', ...} 정도가 되겠다.

 

3) String

문자열은 특정 한 언어에서 알파벳을 선택하여 나열한 유한한 심볼들이다. {aa, aaaa, abbb}정도로 생각하면 된다.

{}와 같이 비어있는 문자열도 string으로 취급한다. 이 경우 λ 혹은 ε으로 나타내면 된다. ({} <- 얘는 공집합이 아니다.)

 

4) Language

언어는 ∑*의 부분집합니다. ∑*이 무엇일까?

∑에 대해 먼저 알아보자면,

1. ∑는 제곱으로 재귀적으로 나타낼 수 있는데, (1) ∑¹ = ∑이고, (2) ∑ⁿ⁺¹ = {xy | x∈∑, y∈∑ⁿ}이다.

예를 들면, ∑ = {0,1}이라고 할 때, ∑² = {xy | x,y ∈∑} = {00, 01, 10, 11}이다.

2. 우리는 ''처럼 비어있는 문자열도 string으로 취급한고 했다. ∑⁰ = {λ} = {ε}라고 나타낸다.

3. ∑* = ∑⁰ ∪ ∑¹ ∪ ∑² ∪ ...이다.

따라서, 우리가 언어 ∑*는 무한집합이다.

 

5) Grammer

문법은 문자열과 알파벳을 이용하여 형식 언어를 구성하는 규칙이다. 형식 문법을 표현하기 위해 정규표현식, 문법 도표 등이 사용된다.

 

Then,

이제 형식 언어의 요소에 대해 알았으니 다시 유한 오토마타에 대한 설명으로 돌아가보자.

 

유한 오토마타 특징

1. 유한 오토마타는 임의의 시점 t에 대해 한가지 상태만을 가질 수 있다.

2. 유한 오토마타에서 현재 상태(current state)란 임의의 주어진 시간의 상태를 칭한다.

3. 유한 오토마타가 한 상태에서 다른 상태로 변하는 것은 어떠한 사건에 의해서만 가능하며, 이를 '전이(transition)'라고 한다.

 

유한 오토마타와 형식 언어의 관계

유한 오토마타가 가장 일반적으로 쓰이는 사례가 문자열을 다루는 regex이다. 언어는 앞에서 언급했듯, 유한한 또는 무한한 문자열의 집합이다. 따라서 우리가 언어 내에 특정 문자열이 있는지 찾는 과정은 매우 고되다.(무한한 문자열의 경우에는 거의 불가능에 가깝다.) 따라서 우리는 이 경우에 유한 오토마타를 사용해 유한 오토마타에게 문자열을 찾으라고 지시한다. 이는 인간이 직접하는 것보다 꽤나 효과적이다. 하지만 우리는 위에서 오토마타가 인식할 수 있는 언어는 제한적이라고 했다. 이를 '정규 언어(regular language)'라고 한다. 따라서 정규 언어는 오토마타가 인식할 수 있는 언어인 형식 언어에 속한다.

 

그럼 어떻게 유한 오토마타가 구성되어 있는지에 대해 알아보도록 하자.

유한 오토마타 구성

직관적으로 유한 오토마타를 나타내기 위해 원 안에 상태(state)를 나타내고 화살표 위에 입력(input)을 작성한다. 위의 사진에서는 input이라는 사건이 발생하여 현재 상태에서 전이 상태로 전이가 일어난다.

위 경우와 같이 현재 상태와 전이 상태가 동일하게 나타날 수 있다.(이 경우를 루프라고 지칭할 예정)

 

이제, 실제 구성요소들을 살펴보자.

위와 같은 유한 오토마타가 존재한다고 가정해보자.

유한 오토마타는 Machine의 M으로 지칭되고 5개의 요소로 이루어져 있다.

M = (Q, ∑, q₀, F, δ)

1) Q = M이 가진 상태의 집합

유한 오토마타 내의 상태의 개수는 유한해야 하므로 Q의 원소의 개수도 유한하다. 위 사진에서는 숫자는 모두 상태이며 Q = {1, 2, 3}으로 나타낼 수 있다.

 

2) ∑ = 입력으로 주어지는 알파벳

형식언어에서 지칭하는 알파벳이 입력으로 주어지는 것이다. 위 사진에서는 영어 알파벳이 모두 input이며, ∑ = {a, b}으로 나타낼 수 있다.

 

3) q₀ = 시작 상태

모든 유한 오토마타는 시작 상태를 가진다. 이는 화살표로 표시가 되며 위 사진에서는 1이 시작상태이다. (q₀ = 1)

 

4) F = 도착 상태의 집합(Final State)

도착 상태는 시작 상태와 다르게 여러개가 될 수 있다. 입력이 끝난 직후에 만약 current state가 도착 상태에 있다면 유한 오토마타는 입력된 문자열이 존재한다고 판단한다. 반면 입력이 끝났을 때 도착 상태에 있지 않으면 그 문자열은 받아들여지지 않는다. 사진에서 도착 상태는 3으로 사진과 같이 원을 두개 겹친 형태로 표현한다. (F = {3})

 

5) δ = 전이 함수

δ는 전이 함수를 나타낸다. 위의 사진의 경우에는 δ(1, a) = 2, δ(2, a) = 3, δ(3, a) = 1, δ(1, b) = 3의 전이 함수들이 있다. 이와 같이 δ(현재 상태, 입력값) = (전이 상태 값)으로 표기하면 된다. (δ에 따라 유한 오토마타의 유형이 달라진다.)

 

유한 오토마타 유형

유한 오토마타에는 3가지 유형이 있다. 결정적 유한 오토마타, 비결정적 유한 오토마타, ε-전이가 있는 비결정적 유한 오토마타로 분류된다.

하나하나 알아보도록 하자.

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

DFA에서 말하는 '결정적'의 의미로 한 입력값이 들어 왔을 때 상태가 전이될 수 있는 경로가 하나여서 전이가 '결정적'이라고 생각하면 기억하기 쉽다. 즉, 모든 상태들은 모든 입력에 대해 각각 한개씩만의 전이 함수를 가지고 있는 것이다.

예를 들면, 아래와 같은 유한 오토마타가 있다.

DFA

이 유한 오토마타는 시작 상태로 1을 가지고 도착 상태로 4를 가진다. Q에 속하는 모든 상태는 입력값 ∑에 속하는 모든 알파벳 a에 대해 한가지 전이만을 가진다. 우리는 이와 같이 모든 상태가 모든 알파벳에 대해 한가지 전이만을 가지는 경우를 DFA라고 한다.

 

2) 비결정적 유한 오토마타(Nondeterministic Finite Automata, NFA)

NFA는 DFA에 속하지 못한 모든 유한 오토마타를 지칭한다. 따라서 이 유한 오타마타 내에서는 어떠한 상태는 두개 이상의 전이를 가지거나 아예 전이를 가지지 않는다.

NFA

위와 같은 유한 오토마타가 있다고 가정했을 때, 상태 1은 δ(1, a) = 2, δ(1, a) = 1이라는 두 개의 전이 함수를 가지고 있는 반면 5는 입력값 a에 대해 어떠한 전이 함수도 가지고 있지 않다. 따라서 이 유한 오토마타는 DFA가 아니므로 NFA이다.

 

3) ε-전이가 있는 비결정적 유한 오토마타 (Nondeterministic Finite Automata with ε-transition, ε-NFA)

ε-NFA는 NFA의 한 특이한 종류이다. 우리는 앞에서 ε가 빈 문자열을 지칭한다고 배웠었다. 따라서, 입력값이 ε인 경우에는 어떠한 사건이 발생하지 않아도 전이가 발생한다.

&epsilon;-NFA

위 유한 오토마타와 같이 ε-전이를 설정하면 특별한 사건, 즉 입력값 없이 전이가 가능한 특별한 상황을 설정할 수 있다.

이와 같이 특별이 ε-전이를 설정할 수도 있지만, 설정하지 않는다 해도 ε-전이는 모든 상태에서 발생한다.

ε는 모든 문자열에 루프로 붙어있는데 따로 설정하지 않는다면 상태에 영향을 주지 못한다. 숫자로 비유하자면 0이 다른 숫자에 아무리 더해져도 영향을 주지 못하는 것과 같다.

모든 상태는 &epsilon;-전이를 가지고 있다.

 

여기까지가 내가 리도스에 대해 알아보기 위해 유한 오토마타에 대해 공부했던 내용이다. 다음 학기에 오토마타 강의를 듣지 않는다면 더 공부할 것 같지는 않는 분야이지만, 잊기 전에 기록을 남겨둔다.

 

참고문헌

https://bestowing.github.io/automata/automata5/

[오토마타 이론] 5. 유한 오토마타의 3가지 유형