오토마타 계층

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

type 3의 제약만 유독 임의로 보인다. 오른쪽 모양까지 왜 묶는지가 안 보이기 때문이다. 만드는 쪽에 조건을 하나 걸어 보면 그 모양이 저절로 나온다.

ab라는 문자열을 만드는 문법은 이렇게 써도 된다.

A → ab

틀린 것은 아니지만 글자 두 개가 한꺼번에 나온다. 여기에 조건을 건다. 왼쪽부터 한 번에 한 글자씩만 내놓자. 그러면 이렇게 쪼갤 수밖에 없다.

A → aB      a를 하나 내놓고, 나머지를 만드는 일은 B에게 넘긴다
B → b       b를 내놓고 끝

유도하면 글자가 하나씩 늘어난다.

A ⇒ aB ⇒ ab

나머지 두 연산도 같은 식이다. 반복 a*는 “하나 내놓고 다시 나에게”를 되풀이한다.

A → aA      a 하나 내놓고, 남은 일은 다시 A에게
A → ε       그만두기

ε이 없으면 멈출 수가 없다. 합집합 a|b는 같은 논터미널에 규칙을 둘 두면 된다.

A → a
A → b

정규표현의 연산은 이 셋뿐이다. a+는 aa*, a?는 a|ε, [a-z]는 a|b|…|z이므로 나머지는 전부 셋을 줄여 쓴 것이다. 그리고 셋을 한 글자씩 내놓는 방식으로 적었더니 나온 모양이 셋뿐이다.

A → aB      터미널 하나 + 논터미널 하나
B → b       터미널 하나
A → ε       빈 것

type 3의 제약은 이 관찰을 규칙으로 적어 놓은 것이다. 오른쪽 모양을 임의로 묶은 것이 아니라, 한 글자씩 만들라고 했더니 남은 모양이다.

여기서 논터미널이 무엇인지가 드러난다. 유도 도중에 abB가 나왔다면 B는 “앞의 ab는 이미 확정됐고, 남은 일은 B가 만들 수 있는 것 아무거나”라는 뜻이다. 읽는 쪽에서 보면 같은 것이 이렇게 읽힌다.

abB     만드는 쪽 :  ab는 다 만들었고 남은 일은 B 담당
        읽는 쪽   :  ab를 읽었고 지금 상태는 B

같은 지점을 양쪽에서 다르게 부르는 것뿐이다. 만드는 쪽에서는 앞으로 만들 것이고, 읽는 쪽에서는 지금까지 읽은 것의 요약이다. 논터미널이 곧 상태다.

그러면 규칙이 곧 전이가 된다. A → aB를 소리 내어 읽으면 “A라는 처지에서 a가 나오면 B라는 처지가 된다”이고, 기계 쪽 표기로는 δ(A, a) = B다.

δ(A, t) = B      ⟺     A → tB
A가 수락 상태     ⟺     A → ε

제약 셋이 각각 기계의 성질이 되는 것도 여기서 나온다.

제약	기계에서	왜
오른쪽에 논터미널이 최대 하나	상태가 한 번에 하나	둘이면 갈래를 들고 다녀야 한다
그 논터미널이 맨 끝에	한 방향으로만 진행	가운데 있으면 양옆으로 자란다
터미널이 하나	한 번에 글자 하나	여럿이면 한꺼번에 확정하는 셈이다

가운데 줄이 aⁿbⁿ과 갈리는 지점이다. S → aSb는 논터미널이 가운데 있어 양옆으로 자라고, 그것이 스택을 부른다.

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

예시

오른쪽이 전부 터미널 + 논터미널 또는 터미널이므로 우선형 정규문법이다. 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 0. 제약이 없으므로 규칙을 쓸 때마다 길이가 늘 수도 줄 수도 있다. 세 글자짜리 문자열을 만드는 도중에 백 글자를 거쳤을 수도 있다는 뜻이다.

S  ⇒ … ⇒  100글자 중간 문자열  ⇒ … ⇒  abc

주어진 문자열이 이 문법으로 만들어지는지 알려면 S에서 규칙을 적용해 가며 찾아야 하는데, 중간 문자열이 얼마나 길어질지 미리 알 수 없다. 작업 공간에 상한을 둘 수 없으니 무한 테이프가 필요하고, 그것이 튜링 기계다.

type 1. 길이가 줄지 않으므로 중간 문자열이 결과보다 길어질 수 없다. 입력이 n글자면 유도 도중의 문자열도 n글자 이하다. 확인할 경우의 수가 유한하니 작업 공간을 입력 길이에 비례해 잡으면 되고, 그것이 선형 유계 오토마타다.

type 2. 왼쪽이 논터미널 하나뿐이라 치환이 주변과 무관해진다. bB → bb는 B 앞이 b일 때만 쓸 수 있지만 B → bb는 B이기만 하면 언제나 쓸 수 있다. 그래서 논터미널마다 따로 펼쳐지고, 유도가 트리가 된다.

S  ⇒  a C a  ⇒  a b a

가운데가 펼쳐지며 양옆이 함께 늘어난다. 여는 것과 닫는 것이 짝을 이루고 마지막에 연 것을 먼저 닫으므로 스택이면 되고, 그것이 푸시다운 오토마타다.

type 3. 오른쪽까지 묶으면 논터미널이 늘 맨 끝에 하나만 남고, 앞부분은 이미 확정되어 되돌아갈 일이 없다. 지금까지 읽은 것을 상태 하나로 들고 가면 되므로 기억장치가 필요 없고, 그것이 유한 오토마타다. 규칙 하나가 전이 하나라는 것은 앞에서 본 대로다.

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

여기까지는 층마다 기억장치가 다르다는 것뿐이다. 층이 실제로 벌어져 있다고 말하려면, 경계마다 아래 층으로는 안 되고 위 층으로만 되는 언어를 내놓아야 한다.

첫 경계의 언어가 앞에서 S → ab | aSb로 만든 L = {aⁿbⁿ | n ≥ 1}이다. PDA는 a마다 push하고 b마다 pop하면 되지만, 유한 오토마타에는 push할 곳이 없다. 적어 둘 데가 없으니 지금 어느 상태에 있는지가 과거에 대해 아는 전부다.

그래서 같은 상태에 도달한 두 입력은 그 뒤로 영원히 구별되지 않는다. 이어지는 동작이 현재 상태와 남은 입력만으로 정해지기 때문이다.

aa   ─▶ q₃ ┐
aaaa ─▶ q₃ ┘  뒤에 무엇을 붙여도 같은 답이 나온다

그런데 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까지는 가능한 구성이 유한하므로, 같은 구성이 다시 나오면 무한루프라고 결론지을 수 있다. 무한 테이프에서는 그 논증이 무너진다. 오래 돌려 보고 안 멈추면 no라고 하면 될 것 같지만, 얼마나가 충분한지 계산할 방법이 없다. 바쁜 비버 함수가 계산 불가능하다는 것이 그 이야기다.

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

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

순서

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

	시점	배경
튜링 기계	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 컴파일러 문법 변환 컴파일러 인라인 캐싱과 특수화 컴파일러 중간언어 컴파일러 컴파일러 생성기