유한 오토마타가 인식하는 언어를 기술하는 방법

이전 포스트에서 유한 오토마타가 입력을 상태 전이만으로 처리하는 모델임을 보았다. 그렇다면 유한 오토마타가 인식할 수 있는 언어의 범위는 어디까지이며, 그 범위를 어떻게 간결하게 기술할 수 있을까? 이 질문에 답하는 것이 바로 정규 표현식(Regular Expression)이다.

프로그래머라면 grep이나 텍스트 에디터에서 정규 표현식을 써 본 경험이 있을 것이다. 그런데 이 도구가 왜 "정규(regular)"라는 이름을 달고 있는지 생각해 본 적이 있는가? 이 이름은 수학적 의미에서의 정규 언어(Regular Language)에서 온 것이며, 정규 표현식이 기술할 수 있는 언어의 집합이 정확히 유한 오토마타가 인식할 수 있는 언어의 집합과 일치하기 때문이다.

정규 표현식의 세 가지 연산

정규 표현식은 세 가지 기본 연산으로 구성된다.

연산표기의미
합집합(Union)R₁ ∪ R₂R₁ 또는 R₂에 속하는 문자열
연결(Concatenation)R₁R₂R₁의 문자열 뒤에 R₂의 문자열을 이어 붙인 것
클리니 스타(Kleene Star)R*R을 0번 이상 반복한 문자열

이 세 가지 연산만으로도 놀라울 정도로 다양한 패턴을 표현할 수 있다. 예를 들어 알파벳 {0, 1} 위에서 (0 ∪ 1)*01이라는 정규 표현식은 "01"로 끝나는 모든 이진 문자열의 집합을 나타낸다. (0 ∪ 1)*이 임의의 이진 문자열을 의미하고, 그 뒤에 "01"이 와야 하므로 결과적으로 "01"로 끝나는 문자열만 수락되는 것이다.

실용적인 정규 표현식 엔진에서는 +(1회 이상 반복), ?(0회 또는 1회), 문자 클래스 같은 편의 연산이 추가되지만, 이들은 모두 세 가지 기본 연산의 축약에 불과하다. R+는 RR*이고, R?는 R ∪ ε이다. 표현력의 관점에서 보면 기본 연산 세 가지로 충분한 셈이다.

클리니의 정리 — 정규 표현식과 유한 오토마타의 동치

정규 표현식과 유한 오토마타 사이에는 깊은 연결이 존재한다. 스티븐 클리니(Stephen Kleene)가 증명한 정리에 따르면, 어떤 언어가 정규 표현식으로 기술될 수 있는 것과 유한 오토마타가 인식할 수 있는 것은 동치이다. 즉, 모든 정규 표현식에 대응하는 유한 오토마타가 존재하고, 모든 유한 오토마타에 대응하는 정규 표현식이 존재한다.

이 동치 관계는 두 방향으로 증명된다. 정규 표현식에서 NFA로의 변환은 톰슨 구성법(Thompson's Construction)을 사용한다. 각 기본 연산(합집합, 연결, 클리니 스타)에 대해 대응하는 NFA 조각을 만들고, 이를 재귀적으로 결합하면 전체 정규 표현식에 대응하는 NFA가 만들어진다. 반대 방향, 즉 유한 오토마타에서 정규 표현식으로의 변환은 상태 제거법(State Elimination)으로 수행할 수 있다. 오토마타의 상태를 하나씩 제거하면서 전이 라벨을 정규 표현식으로 확장해 나가면, 최종적으로 시작 상태와 수락 상태 사이의 경로를 나타내는 정규 표현식을 얻게 된다.

이 정리가 컴파일러에서 중요한 이유는 명확하다. 렉서를 만들 때 토큰 패턴을 정규 표현식으로 기술하면, 이를 기계적으로 NFA → DFA → 최소 DFA로 변환하여 효율적인 렉서를 자동으로 생성할 수 있기 때문이다. lex나 flex 같은 렉서 생성기가 바로 이 원리에 기반한다.

정규 언어의 예시

정규 언어에 해당하는 예시와 그렇지 않은 예시를 구분해 보면 정규 언어의 성격이 더 분명해진다.

정규 언어에 해당하는 것으로는 짝수 개의 0을 포함하는 이진 문자열, 특정 부분 문자열을 포함하는 문자열, 프로그래밍 언어의 식별자 패턴([a-zA-Z_][a-zA-Z0-9_]*), 정수 리터럴, 부동소수점 리터럴 같은 것이 있다. 이런 패턴들은 유한한 상태만으로 판별할 수 있으며, 이전에 본 입력의 횟수를 무한히 기억할 필요가 없다.

반면 정규 언어가 아닌 것으로는 {aⁿbⁿ | n ≥ 0}(a의 개수와 b의 개수가 같은 문자열), 올바르게 중첩된 괄호, 팰린드롬(회문) 같은 것이 있다. 이들은 공통적으로 무한한 카운팅이나 매칭을 요구하며, 유한한 상태만으로는 이를 추적할 수 없다.

펌핑 보조정리 — 정규 언어가 아님을 증명하는 도구

어떤 언어가 정규 언어가 아니라는 것을 엄밀하게 증명할 때 사용하는 도구가 펌핑 보조정리(Pumping Lemma)이다.

펌핑 보조정리의 핵심 직관은 이렇다. 정규 언어를 인식하는 DFA의 상태 수가 유한하기 때문에, 충분히 긴 문자열을 처리하면 반드시 같은 상태를 두 번 이상 방문하게 된다. 같은 상태를 두 번 방문했다는 것은 그 사이의 부분 문자열을 반복하거나 제거해도 여전히 수락된다는 의미이다. 이를 "펌핑"이라고 부른다.

형식적으로는 다음과 같다. 정규 언어 L에 대해 어떤 수 p(펌핑 길이)가 존재하여, 길이가 p 이상인 모든 문자열 s ∈ L은 s = xyz로 분해할 수 있고, 다음 세 조건을 만족한다.

1. |xy| ≤ p
2. |y| ≥ 1
3. 모든 i ≥ 0에 대해, xy^i z ∈ L

이를 이용하여 {aⁿbⁿ | n ≥ 0}이 정규 언어가 아님을 증명할 수 있다. 이 언어가 정규 언어라고 가정하면 펌핑 길이 p가 존재한다. 문자열 aᵖbᵖ를 선택하면, 조건 1에 의해 y는 a로만 구성된다. 그런데 y를 반복하면 a의 개수만 늘어나고 b의 개수는 그대로이므로 xy²z는 a의 개수가 b보다 많아서 언어에 속하지 않는다. 이는 모순이므로 이 언어는 정규 언어가 아닌 것이다.

렉서와의 연결

정규 표현식과 정규 언어가 컴파일러에서 활용되는 가장 직접적인 지점은 렉서(Lexical Analyzer)이다. 렉서의 역할은 소스 코드의 문자 스트림을 의미 있는 토큰(키워드, 식별자, 연산자, 리터럴 등)으로 분리하는 것이다.

각 토큰 종류는 정규 표현식으로 기술된다. 예를 들어 C 언어에서 식별자는 [a-zA-Z_][a-zA-Z0-9_]*, 정수 리터럴은 [0-9]+, 부동소수점 리터럴은 [0-9]+\.[0-9]+([eE][+-]?[0-9]+)? 같은 패턴으로 표현할 수 있다. 이 정규 표현식들을 합쳐서 하나의 DFA로 변환하면, 입력 문자열을 한 번의 스캔으로 토큰화할 수 있는 효율적인 렉서가 만들어진다.

정규 언어의 한계가 곧 렉서의 한계이기도 하다. 중첩된 주석(/* /* */ */)이나 괄호 매칭 같은 구조는 정규 표현식만으로 처리할 수 없으며, 이런 구조를 다루려면 다음 단계인 파서의 영역으로 넘어가야 한다. 이것이 컴파일러가 렉서와 파서를 별도의 단계로 분리하는 근본적인 이유인 것이다.

다음 포스트에서는 정규 언어를 넘어서는 문법 체계인 문맥 자유 문법을 살펴본다.