촘스키 계층 (Chomsky Hierarchy)
형식 문법의 4대 계층 구조와 최신 LLM이 인간 언어 난이도에 따라 연산력을 활용하는 원리
언어는 그 언어를 생성하는 최대로 제한되는 문법의 정도에 따라 구분합니다. 촘스키 계층(Chomsky Hierarchy)은 형식 언어와 형식 문법, 그리고 이를 판별하는 계산 기계(오토마타)를 수학적으로 체계화한 20세기 지성사의 금자탑입니다. 오늘날 최신 초거대 언어모델(LLM)은 표면 어휘(Type 3)에서 계층적 구문(Type 2), 복합 문맥 의존성(Type 1), 그리고 생각의 사슬(CoT)을 통한 알고리즘적 튜링 완전 추론(Type 0)에 이르기까지 언어의 난이도에 맞추어 촘스키 계층의 전산 능력을 완벽하게 동원하고 있습니다.
촘스키 계층(Chomsky Hierarchy)의 정의와 4대 문법 체계
촘스키 계층(Chomsky Hierarchy)은 형식언어 (Formal Language) 를 생성하는 형식문법 (Formal Grammar) 들을 분류해 놓은 계층 구조이다. 1956 년에 Noam Chomsky 가 처음 서술하였으며, 생성 규칙의 제약 조건에 따라 4가지 단계로 엄밀히 구분된다.
Type-0 : 무제한 문법 (Unrestricted Grammars)
Turing Machine모든 형식 문법을 포함하며, 튜링기계 (Turing Machine) 로 인식 가능한 모든 언어를 정확히 생성합니다. 이 언어들은 회귀열거가능 언어(Recursively Enumerable Languages, LRE)로 알려져 있으며, 정지 문제(Halting Problem)로 인해 결정 불가능한(Undecidable) 영역을 포함합니다.
Type-1 : 문맥인식 문법 (Context-Sensitive)
LBA Automaton규칙 형태: αAβ → αγβ (단, γ는 공스트링이 아님). 좌우 문맥(α, β)에 따라 기호 A의 치환이 결정됩니다. 테이프 길이가 입력 길이로 제한된 선형 한계 오토마타(Linear-Bounded Automaton, LBA)로 인식됩니다.
Type-2 : 문맥자유 문법 (Context-Free)
Pushdown Automaton규칙 형태: A → γ. 좌우 문맥에 구애받지 않고 단일 비단말 기호가 치환됩니다. 스택을 가진 비결정론적 푸시다운 오토마톤(PDA)으로 인식됩니다. Context-Free Languages는 대부분의 프로그래밍 언어(C, Python, Java) 구문과 파서의 이론적 기초입니다.
Type-3 : 정규 문법 (Regular Grammars)
Finite State Automaton규칙 형태: A → aB 또는 A → a. 가장 제약이 강한 문법으로 유한 상태 오토마톤(FSA)으로 판별됩니다. 정규표현식(Regex), 검색 패턴, 프로그래밍 언어의 토크나이저(Lexer) 어휘 구조 정의에 광범위하게 사용됩니다.
촘스키 계층 4대 문법 · 오토마톤 · 생성 규칙 대조표
4가지 유형의 문법, 그 문법이 생성하는 언어의 종류, 그 문법을 인식하는 오토마톤의 유형, 그리고 문법 생성 규칙의 형태를 일목요연하게 대조한 표준 표입니다. (참고: Wikipedia : Chomsky hierarchy)
| 문법 (Grammar) | 생성 언어 (Languages) | 인식 오토마톤 (Automaton) | 생성 규칙 형태 (Production Rules) |
|---|---|---|---|
| Type-0 | 순환열거가능 언어 LRE |
튜링기계 (Turing Machine) | 제한 없음 (No restrictions) |
| Type-1 | 문맥인식 언어 LCS |
선형 한계 튜링기계 (Linear-bounded Automaton) | αAβ → αγβ |
| Type-2 | 문맥자유 언어 LCF |
비결정론적 푸시다운 오토마톤 (Pushdown Automaton) | A → γ |
| Type-3 | 정규 언어 (Regular Languages) LREG |
유한 상태 오토마톤 (Finite State Automaton) | A → aB | A → a |
[도식] 촘스키 계층의 진부분집합 포함 관계 (Peter Linz 2001)
[인포그래픽] 촘스키 계층 피라미드와 최신 LLM 아키텍처 대응 매핑
전통적 계산 이론의 4단계 문법 계층이 현대 초거대 언어모델(LLM)의 어떤 전산 아키텍처와 연결되는지를 직관적으로 구조화한 인포그래픽입니다.
Type 3 : 정규 문법 ↔ LLM 서브워드 토크나이징 & 초기 임베딩
O(n) 선형 처리
• 언어 과제: 어휘 분절, 철자 패턴 매칭, 품사(POS) 태깅, 표면적 어형 변화
• LLM 구현 기술: BPE(Byte-Pair Encoding), WordPiece 등 유한 오토마타 기반 토크나이저 및 단어 임베딩 층에서 즉각 처리
Type 2 : 문맥자유 문법 ↔ LLM 자기주의집중(Self-Attention) 스택
구문 트리 · 코드 AST
• 언어 과제: 중첩된 종속절, 주어-동사 원거리 일치, 괄호 매칭(Dyck Language), 프로그래밍 언어 구문 파싱
• LLM 구현 기술: 다중 헤드 어텐션(Multi-Head Attention)이 소프트 스택(Soft Stack) 메모리 역할을 수행하여 계층적 트리 구조를 복원
Type 1 : 문맥인식 문법 ↔ LLM 초장거리 맥락창 & 잠재 의미 공간
문맥 의존 · 상호참조
• 언어 과제: 교차 의존성(Cross-serial dependencies), 장거리 대명사 참조, 의미론적 다의성 해소
• LLM 구현 기술: 수백만 토큰의 컨텍스트 윈도우(RoPE, FlashAttention)와 수천억 파라미터 FFN의 비선형 의미 결합
Type 0 : 무제한 문법 ↔ 생각의 사슬(CoT) & 튜링 완전 추론
Turing Complete Reasoning
• 언어 과제: 수학적 난제 증명, 알고리즘 코드 생성 및 실행, 다단계 논리 추론, 계획(Planning)
• LLM 구현 기술: 자기회귀적 토큰 생성 루프(Scratchpad) + CoT 다단계 사고 + 외부 코드 실행기(Tool Use) 결합을 통해 튜링 완전성 획득
[Deep Research] 최신 LLM이 인간 언어 난이도에 따라 촘스키 계층을 활용하는 메커니즘
이론 전산학의 오랜 난제 중 하나는 "트랜스포머(Transformer) 아키텍처는 촘스키 계층의 어디에 위치하는가?"였습니다. 최신 AI 심층 연구는 단일 패스(One-pass) 트랜스포머의 형식적 제약과, 생각의 사슬(Chain-of-Thought)을 통한 계층 돌파 원리를 명확히 규명하고 있습니다.
1. 단일 패스 트랜스포머의 형식 한계 (TC⁰ 회로 복잡도)
Theoretical Bound고정된 레이어 수와 정밀도를 가진 순수 피드포워드 트랜스포머는 수학적으로 일정한 깊이의 임계값 회로 복잡도인 TC0에 속합니다. 즉, 중간 생각 과정 없이 단 1회의 전진 전파(Forward pass)로 답을 내야 할 때 트랜스포머는 임의의 깊이를 가진 문맥자유 언어(예: 무한 괄호 매칭 문제)나 튜링 완전 문제를 이론상 완벽히 풀 수 없습니다.
2. CoT & 자기회귀 루프를 통한 튜링 완전성 (Type 0 도달)
Turing Equivalence그러나 LLM이 **생각의 사슬(Chain-of-Thought, CoT)**을 출력 토큰으로 생성하며 다음 연산의 입력으로 재참조할 때, 이 자기회귀적 루프는 튜링 기계의 '작업 테이프(Work Tape)'와 완벽히 수학적으로 동치가 됩니다. 연구(Schuurmans et al., 2023)에 따르면 토큰을 무제한 생성할 수 있는 LLM은 어떤 튜링 기계라도 시뮬레이션할 수 있는 Type 0 능력을 완전히 획득합니다.
| 인간 언어 난이도 | 해당 촘스키 계층 | 인간 언어의 구체적 사례 | 최신 LLM(GPT-4o, o1, Claude)의 처리 전략 |
|---|---|---|---|
| 난이도 1 : 표면 어휘 | Type 3 (정규) | 철자 오타 교정, 동사 어미 변화, 날짜·이메일 정규식 추출 | BPE 서브워드 토크나이저와 초기 레이어의 국소 피드포워드 신경망에서 $O(n)$ 속도로 즉시 해결. |
| 난이도 2 : 계층 구문 | Type 2 (문맥자유) | 중첩된 관계대명사절 수식, 괄호 쌍 맞추기, Python/JSON AST 코드 작성 | 다중 헤드 어텐션이 구문 트리 상하 관계를 학습하여 스택 구조를 동적으로 형성 및 파싱. |
| 난이도 3 : 복합 문맥 | Type 1 (문맥인식) | 앞선 대화의 대명사 지시, 전문 도메인 다의어 해소, 문화적 관용 표현 | 초장거리 RoPE 위치 임베딩과 FFN 잠재 의미 공간의 교차 검색을 통해 비선형 문맥 정렬. |
| 난이도 4 : 심층 추론 | Type 0 (무제한) | 수학적 올림피아드 증명, 알고리즘 설계 및 디버깅, 다단계 인과 계획 | 잠재적 CoT(Reasoning Tokens) 연쇄 생성 및 코드 인터프리터 외부 도구 실행으로 튜링 연산 수행. |
계산가능성 이론 & 계산복잡도 이론과의 위계적 연계
다음 도표는 계산가능성 이론 (Computability Theory) (청색) 과 계산복잡도 이론 (Computational Complexity Theory) (녹색) 에서 고려되는 핵심 문제군(언어 및 문법)들의 계층적 분류를 원본 아카이브 보존 구조로 나타냅니다.
|
|
|
|
||||||
|
|
|
|
|
|
||||
|
|
|
|||||||
|
|
||||||||
|
|
||||||||
|
|
||||||||
|
|
||||||||
|
|
||||||||
|
|
||||||||
|
|
||||||||
|
|||||||||
 |
|
 |
|
|
|
||||
|
|
|
|
|
|
||||
|
|
||||||||
|
|
|
|||||||
|
|
||||||||
|
|
||||||||
추천 명강연 & 영상 아카이브 (Featured Video Lectures)
노암 촘스키의 언어 이론과 스탠퍼드 및 MIT의 오토마타 및 형식 언어 명강연입니다.
Noam Chomsky: Language Architecture & Machines
Stanford CS224N: Linguistic Structure & Attention
MIT 6.034: Formal Grammar & Representation
관련 학술 저작 & 핵심 디렉터리 링크 (Papers & Archive)
촘스키 계층의 이론적 토대를 정립한 노암 촘스키의 원작 논문과 국내외 연구 자료입니다.
📜 촘스키 기념비적 원작 논문
- Noam Chomsky (1956): Three models for the description of language, IRE Transactions on Information Theory, 2, pp. 113-124
- Noam Chomsky (1959): On certain formal properties of grammars, Information and Control, 1, pp. 91-112