3.20 튜링 기계와 형식 언어 계층(촘스키 위계)의 관계

1. 촘스키 위계의 정의

촘스키 위계(Chomsky Hierarchy)는 촘스키(Noam Chomsky)가 1956년 “Three Models for the Description of Language“에서 제안한 형식 문법(Formal Grammar)과 형식 언어(Formal Language)의 계층적 분류 체계이다. 이 위계는 문법의 생산 규칙(Production Rule)에 부과되는 제약의 정도에 따라 네 가지 유형으로 분류한다.

형식 문법 $G$ 는 4-튜플 $(V, \Sigma, R, S)$ 로 정의된다:

$V$ : 변수(Variable) 또는 비단말 기호(Nonterminal Symbol)의 유한 집합
$\Sigma$ : 단말 기호(Terminal Symbol)의 유한 집합. $V \cap \Sigma = \emptyset$
$R$ : 생산 규칙(Production Rule)의 유한 집합
$S \in V$ : 시작 변수(Start Variable)

2. 유형 0: 제한 없는 문법(Unrestricted Grammar)

2.1 문법 규칙

생산 규칙 $\alpha \rightarrow \beta$ 에서 $\alpha \in (V \cup \Sigma)^+$ 이고 $\beta \in (V \cup \Sigma)^*$ 이다. 생산 규칙에 대한 제약이 없다.

2.2 인식 기계

제한 없는 문법이 생성하는 언어는 정확히 튜링 기계가 인식하는 언어(재귀적으로 열거 가능한 언어, RE)의 클래스와 일치한다.

$\mathcal{L}(\text{Type 0}) = \text{RE}$

결정 가능성

유형 0 언어의 소속 문제(Membership Problem)—주어진 문자열 $w$ 가 언어 $L$ 에 속하는지—는 일반적으로 결정 불가능(Undecidable)하다. 인식 가능(Recognizable)하지만 결정 불가능한 언어가 이 클래스에 포함된다.

유형 1: 문맥 의존 문법(Context-Sensitive Grammar)

문법 규칙

생산 규칙 $\alpha A \beta \rightarrow \alpha \gamma \beta$ 에서 $A \in V$ 이고, $\alpha, \beta \in (V \cup \Sigma)^*$ 이며, $\gamma \in (V \cup \Sigma)^+$ 이다. 핵심 제약은 생산 규칙의 적용이 비단말 $A$ 의 주변 문맥 $\alpha$ 와 $\beta$ 에 의존한다는 것이다. 또한 $\vert \alpha A \beta \vert \leq \vert \alpha \gamma \beta \vert$ 이므로 문자열이 축소되지 않는다(비축소 조건, Non-Contracting Condition).

인식 기계

문맥 의존 언어는 선형 유계 오토마타(Linear Bounded Automaton, LBA)에 의해 인식된다. LBA는 테이프의 사용 영역이 입력 길이에 비례하여 제한된 비결정적 튜링 기계이다.

$\mathcal{L}(\text{Type 1}) = \text{CSL (Context-Sensitive Languages)}$

2.3 결정 가능성

문맥 의존 언어의 소속 문제는 결정 가능하다. 비축소 조건에 의해 도출 과정의 길이가 유계이므로, 모든 가능한 도출을 체계적으로 탐색하여 소속 여부를 판정할 수 있다. 다만, 최악의 경우 지수적 시간이 소요될 수 있다.

2.4 문맥 의존 언어의 예

$\{a^n b^n c^n \mid n \geq 1\}$ : 세 기호의 수가 같은 문자열
$\{ww \mid w \in \{a, b\}^*\}$ : 동일한 문자열의 반복

3. 유형 2: 문맥 자유 문법(Context-Free Grammar)

3.1 문법 규칙

생산 규칙 $A \rightarrow \gamma$ 에서 $A \in V$ 이고 $\gamma \in (V \cup \Sigma)^*$ 이다. 왼쪽이 반드시 단일 비단말 기호이며, 이 비단말의 대체가 주변 문맥에 독립적(Context-Free)이다.

3.2 인식 기계

문맥 자유 언어는 비결정적 푸시다운 오토마타(Nondeterministic Pushdown Automaton, NPDA)에 의해 인식된다. 푸시다운 오토마타는 유한 오토마타에 스택(Stack)을 추가한 기계이다.

$\mathcal{L}(\text{Type 2}) = \text{CFL (Context-Free Languages)}$

결정 가능성

문맥 자유 언어의 소속 문제는 결정 가능하며, CYK 알고리즘(Cocke-Younger-Kasami Algorithm)에 의해 $O(n^3)$ 시간에 판정된다.

문맥 자유 언어의 예

$\{a^n b^n \mid n \geq 0\}$
올바르게 괄호가 매칭된 문자열
프로그래밍 언어의 구문 구조 대부분

유형 3: 정규 문법(Regular Grammar)

문법 규칙

생산 규칙이 $A \rightarrow aB$ 또는 $A \rightarrow a$ 형태(우선형 정규 문법)이거나, $A \rightarrow Ba$ 또는 $A \rightarrow a$ 형태(좌선형 정규 문법)이다. 여기서 $A, B \in V$ 이고 $a \in \Sigma$ 이다.

인식 기계

정규 언어는 유한 오토마타(Finite Automaton, FA)에 의해 인식된다. 결정적 유한 오토마타(DFA)와 비결정적 유한 오토마타(NFA)는 동등한 인식 능력을 갖는다.

$\mathcal{L}(\text{Type 3}) = \text{REG (Regular Languages)}$

3.3 정규 언어의 예

$\{w \in \{0,1\}^* \mid w \text{는 짝수 개의 0을 포함}\}$
$(ab)^*$ : $ab$ 의 임의 번 반복
정규 표현식(Regular Expression)으로 기술 가능한 모든 패턴

4. 촘스키 위계의 포함 관계

$\text{REG} \subsetneq \text{CFL} \subsetneq \text{CSL} \subsetneq \text{RE}$

각 포함이 엄격(Strict)함을 보이는 분리 언어(Separating Language):

포함 관계	분리 언어
REG $\subsetneq$ CFL	$\{a^n b^n \mid n \geq 0\}$ (CFL이지만 REG가 아님)
CFL $\subsetneq$ CSL	$\{a^n b^n c^n \mid n \geq 1\}$ (CSL이지만 CFL이 아님)
CSL $\subsetneq$ RE	$\text{HALT}$ (RE이지만 CSL이 아님, 결정 불가능)

튜링 기계의 위치

튜링 기계는 촘스키 위계의 최상위 수준(유형 0)에 대응하는 인식 기계이다. 튜링 기계가 인식하는 언어의 클래스(RE)는 촘스키 위계의 모든 하위 수준의 언어 클래스를 포함한다.

문법 유형	언어 클래스	인식 기계	메모리 구조
유형 3	정규	유한 오토마타	유한 상태(메모리 없음)
유형 2	문맥 자유	푸시다운 오토마타	스택(LIFO)
유형 1	문맥 의존	선형 유계 오토마타	유계 테이프
유형 0	RE	튜링 기계	무한 테이프

이 표에서 인식 기계의 메모리 구조가 하위 수준에서 상위 수준으로 갈수록 강력해지는 것을 관찰할 수 있다. 메모리 구조의 강화가 인식 가능한 언어 클래스의 확장을 가능하게 한다.

결정 가능 언어의 위치

결정 가능 언어(재귀 언어)의 클래스는 촘스키 위계에 명시적으로 포함되지 않으나, 다음의 위치에 존재한다:

$\text{CSL} \subseteq \text{Decidable} \subsetneq \text{RE}$

모든 문맥 의존 언어는 결정 가능하며(비축소 조건에 의해), 결정 가능 언어 중 문맥 의존이 아닌 것도 존재한다. 결정 가능 언어는 RE의 진부분집합이다.

5. 위계의 이론적 의의

촘스키 위계는 형식 언어의 복잡도를 인식 기계의 계산 능력과 연결시키는 통합적 프레임워크이다. 이 위계는 자연어 처리(Natural Language Processing), 프로그래밍 언어 설계(Programming Language Design), 컴파일러 이론(Compiler Theory), 계산 복잡도 이론(Computational Complexity Theory)에서 근본적 역할을 수행한다.

인공지능의 관점에서, 자연 언어가 촘스키 위계의 어느 수준에 해당하는지는 자연어 처리의 이론적 난이도를 규정하는 핵심 물음이다. 자연 언어는 문맥 자유 이상의 복잡도를 가진 것으로 분석되며, 이는 자연어 처리가 유한 오토마타나 푸시다운 오토마타를 넘어서는 계산 능력을 요구함을 의미한다.