오토마타 계층

2026.09.02 10:51

오토마타 계층은 형식언어를 표현력에 따라 층으로 나누고, 각 층을 인식하는 기계를 대응시킨 것이다. 문법에 제약을 얼마나 두느냐가 층을 정하고, 그 층을 인식하려면 기계에 무엇이 필요한지가 따라 나온다.

컴파일러의 단계가 이 계층 위에 놓인다. 렉서와 파서가 나뉘는 이유도 여기서 나온다.

형식언어와 촘스키 계층

글자 a와 b만 쓸 수 있다고 하자. 둘을 아무렇게나 늘어놓으면 나오는 경우의 수는 끝이 없을 것이다.

ε, a, b, ab, ba, aab, bba, abab, aaabb, ...

쓸 수 있는 기호의 집합 T = {a, b}를 알파벳이라 하고, 그 기호를 0개 이상 나열해 만들 수 있는 모든 문자열의 집합을 T*라고 한다면, 위의 나열이 T*이다. ε은 아무것도 쓰지 않은 빈 문자열이다.

그리고 T*에서 조건에 맞는 것만 골라낸 부분집합이 언어다. “a를 n개 쓴 뒤 b를 n개 쓴다”는 조건을 언어로 정의한다면 이렇게 된다.

L = { aⁿbⁿ | n ≥ 1 } = { ab, aabb, aaabbb, aaaabbbb, ... }

ab와 aabb는 이 언어에 속하고, ba나 aab는 속하지 않는다.

그런데 여기서 문제는 이 집합이 무한해서 나열할 수 없다는 것이다. 그래서 집합을 적는 대신 그 집합을 만들어 내는 규칙을 적는다.

S → ab
S → aSb

S는 아직 채우지 않은 자리를 가리키는 임시 기호이다. aSb의 S에 다시 ab나 aSb를 넣기를 반복하다가, S가 하나도 남지 않으면 완성이다.

S ⇒ ab
S ⇒ aSb ⇒ a·ab·b            = aabb
S ⇒ aSb ⇒ aaSbb ⇒ aa·ab·bb  = aaabbb

양옆에 하나씩 붙으므로 개수가 저절로 맞게 된다. 이 규칙의 모음을 형식문법이라 부른다.

여기서 기호가 두 종류로 갈린다. ‘그 기호를 나중에 또 바꿔 쓸 수 있느냐’를 기준으로 한다.

터미널: 어떤 규칙의 왼쪽에도 나타나지 않아 한 번 나오면 그대로인 a, b
논터미널: 규칙의 왼쪽에 나타나 언제든 다시 바뀔 수 있는 S

aaSbb처럼 유도 도중의 문자열을 문장형태라 하고, 그중 aaabbb처럼 논터미널이 하나도 남지 않아 더 적용할 규칙이 없는 것을 문장이라 한다. 언어는 T*의 부분집합이므로, 언어에 속하는 것은 문장뿐이다.

문법

만약 문법 하나를 만들고 싶다면 네 가지를 정해야 한다.

무슨 글자를 쓸지
임시 기호로 무엇을 쓸지
규칙이 무엇인지
어디서 시작할지

G = (V_N, V_T, P, S)

V_N : 논터미널 목록      위 예에서 {S}
V_T : 터미널 목록        {a, b}          (V_N 과 겹치지 않는다)
P   : 생성규칙 목록      {S → ab, S → aSb}
S   : 시작기호           S

생성규칙 α → β에서 왼쪽 α는 비어 있으면 안 되지만 오른쪽 β는 비어도 된다. 바꿀 대상이 없는 규칙은 의미가 없는 반면 기호를 지우는 규칙(A → ε)은 필요하기 때문이다. 이 차이를 α ∈ V⁺, β ∈ V*로 적는다. (*가 0개 이상, ⁺가 1개 이상임)

촘스키는 생성규칙의 양쪽에 어떤 제약을 두는지에 따라 문법을 네 종류로 나눴다.

type	생성규칙 형태	이름
0	`γαδ → γβδ` (제약 없음)	unrestricted
1	`α → β`, 단 `\|α\| ≤ \|β\|`	context-sensitive
2	`A → γ`, 단 `A ∈ V_N`	context-free
3	`A → tB`, `A → t` (또는 `A → Bt`, `A → t`)	정규문법

위에서 아래로 갈수록 제약이 세지고 표현력이 줄어든다.

type 0 ⊃ type 1 ⊃ type 2 ⊃ type 3

제약이 하나씩 추가되는 순서로 읽으면 된다.

type 0에서 길이가 줄어들 수 없다는 조건을 걸면 type 1
type 1에서 왼쪽이 논터미널 하나여야 한다고 하면 type 2. 왼쪽에 문맥이 없으므로 context-free다
type 2에서 오른쪽이 터미널 하나 + 논터미널 하나(또는 터미널 하나)여야 한다고 하면 type 3

어떤 문법이 어디에 속하는지는 가장 제약이 센 쪽부터 확인하면 된다.

예시

오른쪽이 전부 터미널 + 논터미널 또는 터미널이므로 우선형 정규문법이다. L = {aⁿbaᵐ | n, m ≥ 1}을 생성한다.
```
S → aS | aB,  B → bC,  C → aC | a
```
S → aCa의 오른쪽이 정규문법 형태가 아니지만, 왼쪽이 논터미널 하나이므로 context-free다. L = {aⁿbaⁿ | n ≥ 1}을 생성한다. 여는 a의 개수와 닫는 a의 개수가 같아야 한다는 점에서 정규문법과 갈린다.
```
S → aCa,  C → aCa | b
```
bB → bb처럼 왼쪽이 논터미널 하나가 아니다. 하지만 |α| ≤ |β|는 만족하므로 context-sensitive다. bB → bb는 “B 앞에 b가 올 때만” 적용되므로, 왼쪽의 b가 문맥이다. 이름의 유래다.
```
A → abC,  bB → bb,  A → aABC,  CB → BC,  bC → bb
```

인식기

문법이 S에서 문자열을 만들어 낸다면, 반대로 완성된 문자열을 읽어 그 언어에 속하는지 답하는 기계가 인식기이다.

인식기가 가진 것은 상태와 기억장치뿐이고, 상태의 종류는 유한하다. 계층마다 필요한 기억장치의 방식이 달라진다. 층이 나뉘는 것은 경계마다 아래 층으로는 안 되고 위 층으로만 되는 언어가 있기 때문이다.

층	인식기	기억장치	할 수 있는 일
type 3 정규언어	유한 오토마타	X	정해진 모양인지 확인
type 2 context-free	푸시다운 오토마타	스택	중첩. 마지막에 연 것을 먼저 닫기
type 1 context-sensitive	선형 유계 오토마타	입력 길이에 비례하는 테이프	떨어진 위치끼리 대조
type 0 재귀 열거 집합	튜링 기계	무한 테이프	계산 가능한 전부

첫 경계의 언어가 앞에서 S → ab | aSb로 만든 L = {aⁿbⁿ | n ≥ 1}이다. PDA는 a마다 push하고 b마다 pop하면 된다. 유한 오토마타에는 그럴 곳이 없다. 읽어 온 내용에 대해 아는 것이 지금 몇 번 상태에 있는가 하나뿐이라, 상태가 100개면 지나온 역사를 100가지로만 구별한다.

그런데 a를 하나 읽은 뒤와 둘 읽은 뒤는 달라야 한다. 뒤에 와야 할 b의 개수가 다르다. 구별할 상황은 무한하고 상태는 유한하니, a를 1개, 2개, 3개… 읽은 뒤 도달하는 상태는 어딘가에서 반드시 겹친다. a i개와 a j개가 같은 상태로 간다고 하자(i ≠ j). 그 뒤로 기계에게 둘은 구별되지 않는 입력이므로, b를 i개 이어 붙이면 같은 답이 나온다.

aⁱbⁱ   속한다
aʲbⁱ   속하지 않는다

답이 갈려야 하는 두 입력에 같은 답을 낸다. 그런 유한 오토마타는 없다. 펌핑 보조정리로 부르는 논증의 알맹이가 이것이다.

정규표현으로 흉내 내려 해도 안 된다.

re.compile(r'^a+b+$').match("aaabb")   # True — 개수가 달라도 통과한다

a+b+는 개수 관계를 표현하지 못한다. 상한을 두고 나열하면 어떨까.

re.compile(r'^(?:ab|aabb|aaabbb|aaaabbbb)$')
# n=1..4 → True,  n=5,6 → False

상한까지만 되고 그 위는 안 된다. 이걸 flex로 만들어 DFA 상태 수를 재 보면 대가가 드러난다.

상한 n≤3   →  DFA 상태 16개
상한 n≤6   →  DFA 상태 34개
상한 n≤12  →  DFA 상태 97개
상한 n≤24  →  DFA 상태 331개

상한을 두 배로 늘리면 상태가 세 배 넘게 는다. 대략 n²에 비례하고, 상한을 없애려면 상태가 무한히 필요하다. 유한 오토마타의 정의에 어긋난다.

다음 경계에는 aⁿbⁿcⁿ이 있다. a와 b는 스택으로 맞출 수 있지만 그러면서 스택이 비므로, c를 셀 차례에는 개수가 남아 있지 않다. 여기서 크기가 기준이 아니라는 것도 드러난다. PDA의 스택은 무한히 자라고 LBA의 테이프는 입력 길이로 묶여 있는데도 LBA가 더 세다. 스택은 꼭대기만 만질 수 있어 지나간 것을 다시 보지 못하고, 테이프는 아무 칸이나 읽고 쓴다. 접근 규칙이 계층을 만든다.

맨 위에서는 언어 이름부터 달라진다. type 0의 재귀 열거 집합은 튜링 기계가 yes를 내는 문자열의 모음이라는 뜻인데, 속하지 않는 문자열에는 no를 내는 대신 영영 멈추지 않을 수 있어서 판정이라고 부르지 못한다.

절벽이 여기다. type 1까지는 정지 여부를 판정할 수 있다. LBA는 테이프가 입력 길이로 묶여 있어 가능한 구성이 유한하고, 같은 구성이 다시 나오면 무한루프다. 무한 테이프에서는 이 논증이 무너진다. 오래 돌려 보고 안 멈추면 no라고 하면 될 것 같지만, 얼마나가 충분한지 계산할 방법이 없다. 바쁜 비버 함수가 계산 불가능하다는 것이 그 이야기다.

그래서 아래 두 층은 계산 가능성 논의에 쓰이지 컴파일러 구현에 나오지 않는다. 실제로 쓰이는 것은 type 3과 type 2다.

하나의 컴파일러를 만드는 작업은 주어진 언어를 인식할 수 있는 인식기를 만드는 작업이라고 할 수 있다.

순서

문법과 기계가 짝을 이루지만, 넷이 한 자리에서 같이 나온 것은 아니다.

	시점	배경
튜링 기계	1936 Turing	힐베르트의 결정문제
유한 오토마타	1943 McCulloch–Pitts, 1951 Kleene	신경망 모형, 정규사건
촘스키 계층	1956, 1959 Chomsky	자연어 기술
선형 유계 오토마타	1960 Myhill, 1964 Kuroda	type 1에 맞는 기계 찾기
푸시다운 오토마타	1961 Oettinger, 1963 Schützenberger	type 2에 맞는 기계 찾기

위아래 끝은 기계가 20년 먼저다. 촘스키는 있던 것을 가져다 붙였다. type 0 문법과 튜링 기계의 대응부터가 Post의 재작성 시스템(1943)이 튜링 기계와 동치라는 결과를 경유한 것이고, 유한상태 마르코프 모형으로 영어를 기술할 수 없다는 논증이 1956년 논문의 동기였다.

가운데 두 층은 반대다. 문법을 먼저 정의해 놓고 이것을 인식하는 기계가 무엇인지를 5년쯤 뒤에 찾았다. 생성규칙의 제약으로 그은 선과 기억장치로 그은 선이 같은 자리에 떨어진다는 것이 계층의 내용인데, 그 일치를 확인하는 작업이 실제로 일어난 곳은 이 두 층이다.

절벽 아래를 재는 일은 따로 진행됐다. 바쁜 비버 함수는 1962년 Radó가 정의했다. 상태 n개짜리 튜링 기계 중 멈추는 것이 찍을 수 있는 1의 최대 개수이고, 이 값을 알면 그만큼 돌려 보고 no를 낼 수 있으므로 정지 문제가 풀린다. 그래서 계산 불가능하다. 상태 5개짜리의 값이 2024년에야 증명됐고(Σ(5) = 4098, 4700만 스텝), 6개는 미해결이다.

스택 하나를 더하면

푸시다운 오토마타는 유한 오토마타에 스택을 붙인 것이다. 구성원소가 다섯에서 일곱으로 늘어난다.

M = (Q, Σ, T, δ, q₀, z₀, F)

Q  : 상태들의 유한집합
Σ  : 입력기호들의 유한집합
T  : 스택기호들의 유한집합          ← 추가
δ  : Q × (Σ ∪ {ε}) × T → Q × T*   ← 스택 top을 보고, 스택에 쓴다
q₀ : 시작상태
z₀ : 스택의 시작기호                ← 추가
F  : 종료상태들의 집합

달라진 것은 전이함수다. δ(q, a, z) = {(p, r)}는 “상태 q에서 입력 a를 보고 스택 top이 z이면, 상태를 p로 옮기고 z를 pop한 뒤 r을 push한다”는 뜻이다.

L = {0ⁿ1ⁿ | n ≥ 1}을 인식하는 PDA는 이렇게 된다.

δ(q₀, 0, z) = {(q₁, 0z)}      첫 0을 보고 스택에 0을 쌓는다
δ(q₁, 0, 0) = {(q₁, 00)}      0을 볼 때마다 하나씩 더 쌓는다
δ(q₁, 1, 0) = {(q₂, ε)}       1이 나오기 시작하면 하나씩 pop
δ(q₂, 1, 0) = {(q₂, ε)}
δ(q₂, ε, z) = {(q₀, ε)}       스택 바닥에 닿으면 개수가 맞은 것

개수를 세는 일을 상태가 아니라 스택 높이가 맡는다. 스택은 무한히 자랄 수 있으므로 n에 상한이 없다.

유한 오토마타에 DFA와 NFA가 있었듯 푸시다운 오토마타에도 결정적(DPDA)과 비결정적(NPDA)이 있다. 그런데 여기서는 둘이 동치가 아니다. L = {wwᴿ}(뒤집어도 같은 문자열)처럼 NPDA로만 인식되는 언어가 있다. 어디가 한가운데인지 미리 알 수 없어 추측이 필요하기 때문이다. 유한 오토마타에서 부분집합 구성으로 NFA를 DFA로 바꿀 수 있었던 것과 대비된다.

실용적으로는 이 차이가 LR 파싱의 배경이 된다. LR 파서는 결정적 푸시다운 오토마타이고, 스택과 파싱표로 백트래킹 없이 동작한다. LR(k) 문법이 아닌 context-free 문법이 존재한다는 사실이 DPDA ⊊ NPDA의 다른 표현이다. context-free 안에서도 LL(k) ⊊ LR(k) ⊊ 결정적 context-free ⊊ context-free로 갈리고, 파서를 고를 때 실제로 보게 되는 것은 촘스키 계층이 아니라 이쪽이다.

컴파일러가 이 계층 위에 놓이는 방식

앞 단계가 계층에 그대로 대응한다.

소스 문자열
│
├─ 렉서    : 유한 오토마타      (토큰은 정규언어)
│
├─ 파서    : 푸시다운 오토마타   (문장 구조는 context-free)
│
└─ 의미분석 : ???

토큰은 왜 정규언어로 충분한가. 식별자, 정수, 연산자, 예약어는 개수를 셀 필요가 없다. [a-zA-Z_][a-zA-Z0-9_]*는 길이에 상한이 없어도 상태 두 개면 된다.

문장 구조는 왜 스택이 필요한가. 중첩 괄호, 중첩 블록, 중첩 if가 전부 aⁿbⁿ 문제다. 여는 것과 닫는 것의 개수가 맞아야 하고 깊이에 상한이 없다.

그래서 컴파일러의 앞 단계가 둘로 나뉜다. 하나로 합칠 수도 있지만 그러면 전부를 푸시다운 오토마타로 처리해야 한다. 토큰 인식처럼 상태만으로 되는 일까지 스택을 들고 하는 셈이라 손해다. 렉서를 표 구동으로 만들 수 있는 것도 정규언어이기 때문이다.

경계가 흔들리는 경우도 있다. 파이썬의 들여쓰기는 깊이를 세야 하므로 정규언어가 아닌데, 토크나이저가 들여쓰기 스택을 들고 INDENT/DEDENT를 합성해서 처리한다. 렉서가 계층을 한 칸 넘어간 것이고, 그 대가로 tok_state에 스택이 여럿 생겼다. 반대로 파서가 의미 정보를 참조하기도 한다. C의 T * x;가 곱셈인지 포인터 선언인지는 T가 타입 이름인지 알아야 정해지고, 그래서 파서가 기호표를 들여다본다(lexer hack).

프로그래밍 언어는 context-free 문법으로 정의된다. 하지만 실제로 유효한 프로그램의 집합은 context-free 언어가 아니다.

int x;
y = 1;

‘변수는 선언된 뒤에 써야 한다’는 규칙은 context-free 문법으로 쓸 수 없다. 이름의 개수에 상한이 없으므로, 선언 목록과 사용 목록을 대조하는 일이 aⁿbⁿ보다 어려운 문제다. 타입이 맞는지, 인자 개수가 맞는지도 마찬가지다.

이론적으로는 context-sensitive에 속하지만, context-sensitive 문법으로 언어를 정의하는 컴파일러는 없다. 파싱이 비현실적으로 비싸기 때문이다. 실무의 답은 계층을 올리는 대신 단계를 나누는 것이다.

context-free 문법으로 파싱 → AST
   ↓
기호표를 들고 트리를 순회하며 나머지 규칙을 검사   ← 의미 분석

기호표는 이름에 속성을 붙여 두는 자료구조이고, 스코프 해석과 타입 검사가 여기서 일어난다. “문맥”을 문법이 아니라 자료구조로 들고 다니는 셈이다.

참고

컴파일러 Pratt 파싱 컴파일러 객체 표현과 GC 컴파일러 문법 변환 컴파일러 인라인 캐싱과 특수화 컴파일러 중간언어 컴파일러 컴파일러 생성기