유한 오토마타의 소개
지금까지 우리는 전이도(Transition Diagram)를 통해 토큰을 인식하는 방법을 살펴보았다. 이제 Lex가 입력 프로그램을 어휘 분석기로 바꾸는 방법의 핵심인 유한 오토마타(Finite Automata) 형식을 살펴보겠다.
유한 오토마타는 본질적으로 전이도와 같은 그래프이지만 몇 가지 차이점이 있다.
- 유한 오토마타는 인식기(recognizer) 이다. 즉, 각 가능한 입력 문자열에 대해 단순히 "yes" 또는 "no"라고 대답한다.
- 전이도와 달리 유한 오토마타는 ε(빈 문자열) 으로 레이블된 간선을 가질 수 있다.
유한 오토마타는 두 종류가 있다.
| 유형 | 설명 |
|---|---|
| 비결정적 유한 오토마타 (NFA) | 간선의 레이블에 제한이 없다. 같은 상태에서 동일한 심볼로 레이블된 여러 간선이 나갈 수 있고, ε으로 레이블된 간선도 가능하다. |
| 결정적 유한 오토마타 (DFA) | 각 상태에서, 입력 알파벳의 각 심볼에 대해 정확히 하나의 간선이 그 상태를 떠난다. |
결정적 유한 오토마타와 비결정적 유한 오토마타는 둘 다 정규 표현식이 나타낼 수 있는 것과 정확히 같은 언어를 인식할 수 있다.
비결정적 유한 오토마타 (NFA)
비결정적 유한 오토마타(NFA) 는 다음과 같이 구성된다.
- 유한한 상태들의 집합 S
- 입력 심볼들의 집합 Σ (입력 알파벳). ε은 어떤 입력 알파벳의 멤버도 아니라고 가정한다.
- 전이 함수 가 상태와 Σ ∪ {ε}의 심볼을 받아 상태들의 집합을 준다.
- S의 상태 중 하나인 시작 상태(start state) s₀
- S의 부분집합 F인 수락 상태(accepting states) 또는 종료 상태의 집합
NFA나 DFA 모두 전이 그래프(transition graph) 로 표현할 수 있다. 노드는 상태이고, 레이블된 간선은 전이 함수를 나타낸다. 상태 s에서 상태 t로의 간선이 a로 레이블되어 있다면, 상태 s와 입력 a에 대한 다음 상태 중 하나가 t라는 것이다.
NFA 예제
위 그림은 언어 (a|b)*abb를 인식하는 NFA의 전이 그래프이다. 이 NFA의 전이 테이블은 다음과 같다.
→ 해당 기호를 해석하자면, a와 b로 이루어진 어떤 문자열이든 상관없지만, 반드시 끝은 'abb'로 끝나야 한다 라는 뜻입니다.
| STATE | a | b | ε |
|---|---|---|---|
| 0 | {0, 1} | {0} | ∅ |
| 1 | ∅ | {2} | ∅ |
| 2 | ∅ | {3} | ∅ |
| 3 | ∅ | ∅ | ∅ |
상태 0에서 입력 a를 보면 상태 0에 머물 수도 있고 상태 1로 전이할 수도 있다. 이 오토마타가 비결정적 이라고 불리는 이유가 바로 이것이다. 상태 0에서 입력 심볼 a를 보면, 상태 0으로 갈 수도 있고 상태 1로 갈 수도 있다.
전이 테이블의 장점은 주어진 상태와 입력에 대한 전이를 쉽게 찾을 수 있다는 것이다. 단점은 입력 알파벳이 클 때, 대부분의 상태가 대부분의 입력 심볼에 대해 어떤 이동도 없더라도 많은 공간을 차지한다는 것이다.
NFA의 입력 문자열 수락
NFA가 입력 문자열 x를 수락(accept) 한다는 것은 전이 그래프에서 시작 상태에서 수락 상태 중 하나로 가는 경로가 존재하고, 그 경로를 따라가며 심볼들을 이으면 x가 된다는 것이다.
ε-레이블은 해당 경로에서 무시된다. 즉, 경로 상의 레이블들을 모으면 빈 문자열은 무시되므로 x가 만들어진다.
입력 `aabb`의 수락 과정
입력 문자열 aabb에 대해 NFA가 어떤 경로들을 따라갈 수 있는지 살펴보자.
- 경로 1: 0 →(a)→ 0 →(a)→ 0 →(b)→ 0 →(b)→ 0 (수락 상태 아님)
- 경로 2: 0 →(a)→ 0 →(a)→ 1 →(b)→ 2 →(b)→ 3 (수락 상태!)
- 경로 3: 0 →(a)→ 1 →(b)→ ? (상태 1에서
a에 대한 전이 없음, 막다른 골목)
경로 2가 수락 상태에 도달하므로, 문자열 aabb는 이 NFA에 의해 수락된다.
NFA에서 어떤 문자열이 수락되려면 모든 경로가 수락 상태로 끝날 필요는 없다. 단 하나의 경로라도 수락 상태에 도달하면 그 문자열은 수락된다.
결정적 유한 오토마타 (DFA)
결정적 유한 오토마타(DFA) 는 비결정적 유한 오토마타(NFA)의 특수한 경우이다.
- 어떤 상태에서도 ε으로 레이블된 간선이 없다.
- 각 상태 s와 각 입력 심볼 a에 대해, s에서 나가는 a로 레이블된 간선이 정확히 하나 있다.
DFA는 각 입력에 대해 최대 하나의 경로 만 존재하므로, 컴퓨터 프로그램으로 NFA를 시뮬레이션하는 것보다 DFA를 시뮬레이션하는 것이 더 쉽다. 왜냐하면 NFA의 전이 함수는 다중값이어서 여러 상태를 동시에 추적해야 하기 때문이다.
DFA 예제
위 그림은 NFA와 같은 언어 (a|b)*abb를 인식하는 DFA의 전이 그래프이다. 이 DFA의 전이 테이블은 다음과 같다.
| STATE | a | b |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 1 | 2 |
| 2 | 1 | 3 |
| 3 | 1 | 0 |
각 상태에서 각 입력에 대해 정확히 하나의 전이 만 정의되어 있음을 확인할 수 있다.
DFA 시뮬레이션 알고리즘
s = s₀;
c = nextChar();
while (c != eof) {
s = move(s, c);
c = nextChar();
}
if (s가 수락 상태) return "yes";
else return "no";
함수 move(s, c)는 상태 s에서 입력 문자 c를 보고 전이하는 상태를 반환한다. 함수 nextChar()는 입력 문자열의 다음 문자를 반환한다.
입력 문자열 ababb가 주어지면, 이 DFA는 상태 시퀀스 0, 1, 2, 1, 2, 3을 거쳐 "yes"를 반환한다.
NFA와 DFA의 비교
NFA와 DFA는 표현력 측면에서 동등하다. 즉, NFA로 인식할 수 있는 언어는 DFA로도 인식할 수 있고, 그 역도 성립한다.
| 관점 | NFA | DFA |
|---|---|---|
| 같은 심볼에 여러 전이 | 가능 | 불가능 |
| ε-전이 | 가능 | 불가능 |
| 시뮬레이션 | 복잡 (여러 경로 추적) | 단순 (단일 경로) |
| 구성 용이성 | 정규 표현식에서 직접 구성 가능 | NFA로부터 변환 필요 |
| 상태 수 | 적을 수 있음 | 최악의 경우 지수적 증가 |
모든 DFA는 본질적으로 NFA이기도 하다. DFA는 NFA의 특수한 경우로, ε-전이가 없고 각 상태에서 각 심볼에 대해 정확히 하나의 전이만 있는 NFA이다.
정규 표현식에서 NFA를 구성하는 것은 쉽지만, DFA를 직접 구성하기는 어렵다. 그래서 보통 정규 표현식 → NFA → DFA의 변환 과정을 거친다.
전이도와 유한 오토마타의 관계
전이도는 사실 유한 오토마타의 시각적 표현에 해당한다.
| 전이도 요소 | 유한 오토마타 요소 |
|---|---|
| 원(노드) | 상태 (S) |
| 화살표(간선) | 전이 함수 |
| 화살표 위의 레이블 | 입력 심볼 (Σ) |
| 시작을 나타내는 화살표 | 시작 상태 (s₀) |
| 이중 원 | 수락 상태 (F) |
전이도는 유한 오토마타를 그래프 형태로 표현한 것이며, 전이 테이블은 표 형태로 표현한 것이다. 두 표현 방식은 본질적으로 동일한 정보를 담고 있다.