왜 오토마타부터 시작하는가?

컴파일러를 공부하겠다고 마음먹으면 대부분 바로 파서나 코드 생성부터 보고 싶어한다. 그런데 실제로 컴파일러의 각 단계를 깊이 이해하려면 그 밑바닥에 있는 이론을 피할 수 없다. 렉서는 유한 오토마타로 동작하고, 파서는 푸시다운 오토마타로 동작한다. 이 이론을 모르고 컴파일러를 만들면 왜 그렇게 설계되었는지를 이해하지 못하는 것이다.

이 시리즈는 오토마타 이론에서 출발하여 실제 컴파일러를 구현하는 것까지를 다룬다. 첫 번째 주제는 가장 기초적인 계산 모델인 유한 오토마타이다.

유한 오토마타의 개념

유한 오토마타(Finite Automaton)는 유한한 수의 상태를 가지며, 입력을 한 글자씩 읽으면서 상태를 전이하는 추상적인 기계이다. 입력을 모두 읽은 후 현재 상태가 수락 상태이면 해당 입력을 수락하고, 그렇지 않으면 거부한다.

일상에서도 유한 오토마타와 유사한 구조를 접할 수 있다. 자판기를 생각해 보면, 동전을 넣을 때마다 상태가 바뀌고, 충분한 금액이 되면 음료를 배출하는 상태로 전이된다. 신호등도 마찬가지이다. 빨강, 노랑, 초록이라는 유한한 상태를 시간에 따라 순환하는 것이다.

형식적으로 유한 오토마타는 다섯 가지 요소로 정의된다.

요소설명
Q상태의 유한 집합
Σ입력 알파벳의 유한 집합
δ전이 함수 (Q × Σ → Q)
q₀시작 상태
F수락 상태의 집합

이 다섯 요소가 주어지면 하나의 유한 오토마타가 완전히 결정된다. 중요한 점은 메모리가 없다는 것이다. 유한 오토마타는 현재 상태만 기억할 수 있으며, 이전에 어떤 입력을 읽었는지는 상태를 통해 간접적으로만 반영된다.

DFA와 NFA

유한 오토마타는 결정적 유한 오토마타(DFA)와 비결정적 유한 오토마타(NFA)로 나뉜다.

DFA에서는 각 상태에서 주어진 입력에 대해 전이할 수 있는 다음 상태가 정확히 하나이다. 모호함이 없기 때문에 구현이 직관적이다. 현재 상태와 입력 글자만 보면 다음 상태가 결정되는 것이다.

NFA에서는 하나의 입력에 대해 여러 상태로 동시에 전이할 수 있으며, 입력을 읽지 않고도 전이하는 ε-전이(엡실론 전이)가 허용된다. 과연 이런 비결정성이 DFA보다 더 강력한 계산 능력을 부여하는 것일까? 그렇지 않다. NFA가 인식할 수 있는 언어의 집합은 DFA가 인식할 수 있는 언어의 집합과 정확히 동일하다. 이것이 오토마타 이론에서 가장 중요한 결과 중 하나이다.

다만, 표현의 편의성에서는 차이가 있다. NFA는 동일한 언어를 훨씬 적은 상태로 표현할 수 있는 경우가 많다. 이 때문에 정규 표현식을 오토마타로 변환할 때 먼저 NFA를 구성하고, 이를 DFA로 변환하는 과정을 거치는 것이 일반적이다.

DFA의 예시

이진 문자열에서 "01"이라는 부분 문자열을 포함하는 입력을 수락하는 DFA를 생각해 보자.

상태: {S0, S1, S2}
알파벳: {0, 1}
시작 상태: S0
수락 상태: {S2}

전이:
  S0 --0--> S1
  S0 --1--> S0
  S1 --0--> S1
  S1 --1--> S2
  S2 --0--> S2
  S2 --1--> S2

S0은 아직 "0"을 보지 못한 상태이다. "0"을 읽으면 S1으로 전이하여 "0"을 본 상태가 된다. S1에서 "1"을 읽으면 "01" 패턴을 완성하여 S2로 전이하고, S2는 수락 상태이므로 이후 어떤 입력이 와도 수락 상태를 유지한다. 이 과정에서 오토마타는 별도의 메모리 없이 상태 전이만으로 패턴 매칭을 수행하는 것이다.

NFA에서 DFA로의 변환

모든 NFA는 동등한 DFA로 변환할 수 있다. 이 변환을 부분집합 구성법(Subset Construction)이라고 부른다.

핵심 아이디어는 NFA에서 동시에 존재할 수 있는 상태들의 집합을 DFA의 하나의 상태로 대응시키는 것이다. NFA의 상태가 n개이면, DFA의 상태는 최대 2ⁿ개가 될 수 있다. 실제로는 도달 가능한 상태만 생성하므로 이보다 훨씬 적은 경우가 대부분이지만, 최악의 경우 상태가 지수적으로 증가할 수 있다는 점은 중요한 고려사항이다.

이 변환이 컴파일러와 어떤 관련이 있는가? 렉서를 구현할 때 정규 표현식을 먼저 NFA로 변환하고(Thompson 구성법), 이를 DFA로 변환한 후(부분집합 구성법), DFA를 최소화하여 최적의 렉서를 만드는 것이 표준적인 절차이다. 이론이 곧 실제 구현으로 이어지는 셈이다.

유한 오토마타의 한계

유한 오토마타가 인식할 수 없는 언어도 존재한다. 대표적인 예가 괄호 매칭이다. "((()))"처럼 열린 괄호와 닫힌 괄호의 수가 같은지를 확인하려면 열린 괄호의 수를 세어야 한다. 그런데 유한 오토마타는 유한한 상태만 가지므로 임의의 깊이의 괄호를 추적할 수 없다.

이러한 한계는 프로그래밍 언어의 문법을 처리할 때 직접적으로 드러난다. 중첩된 블록, 재귀적 함수 호출, 괄호 매칭 같은 구조는 유한 오토마타만으로는 다룰 수 없는 것이다. 이를 해결하기 위해 스택이라는 무한한 메모리를 추가한 모델이 필요하며, 이것이 나중에 다룰 푸시다운 오토마타이다.

다음 포스트에서는 유한 오토마타가 인식하는 언어를 기술하는 방법인 정규 표현식과 정규 언어를 살펴본다.