촘스키 위계

촘스키 위계(Chomsky Hierarchy)는 형식언어를 생성하는 형식문법의 부류들 사이의 위계를 말한다. 노엄 촘스키가 1956년에 제시하였다.

언어는 형식적으로 문장들의 집합으로 정의될 수 있고, 문장은 형식적으로 기호들의 연쇄로 정의될 수 있다.

예를 들어, $T =$ {ㄱ, ㄴ, ㄷ, ㄹ, ..., ㅎ, ㅏ, ㅑ, ㅓ, ㅕ, ..., ㅡ, ㅣ}라고 했을 때 다음과 같은 언어들이 있을 수 있다.

$L_1 =$ {ㄱㅏ, ㄴㅏ, ㄷㅏ, ㄹㅏ, ..., ㅎㅏ}

$L_2 =$ {ㄱㅏㄷㅏ, ㅅㅏㄷㅏ, ㅈㅏㄷㅏ, ㅊㅏㄷㅏ, ㅌㅏㄷㅏ, ㅍㅏㄷㅏ, ㅎㅏㄷㅏ}

$L_3 =$ {ㄱㄱㅏㄷㅏ, ㄷㄷㅏㄷㅏ, ㅅㅅㅏㄷㅏ, ㅈㅈㅏㄷㅏ}

문법은 형식적으로 기호들의 집합에 그 기호들로부터 문장을 만드는 규칙이 부여된 것으로 정의될 수 있다.

$G = (V_N, V_T, P, S)$

형식문법을 기술하는 데 있어서 몇가지 기호 사용의 관례가 있다.

$V_N$ 의 윈소인 비말단 기호는 $A, B, C$ 등의 영문자 대문자로 표기한다.
$V_T$ 의 원소인 말단 기호는 $a, b, c$ 등의 영문자 소문자로 표기한다.
$V (=V_N \cap V_T)$ 의 원소는 $\alpha, \beta, \gamma$ 등 그리스문자로 표기한다. 즉, 비말단과 말단을 구별하지 않을 때이다.
빈 문자열은 $\epsilon$ 로 표기한다.

이렇게 정의된 형식문법은 생성규칙에 어떠한 제약이 있는가에 따라서 다음과 같이 나누어질 수 있다.

제약없는 문법(UG, unrestricted grammar). 생성규칙(production rule)에 제약을 두지 않는다. 단,

\alpha \rightarrow \beta

에서

\alpha \neq \epsilon

문맥의존문법(CSG, context-sensitive grammar). 모든 생성 규칙은

\alpha \rightarrow \beta

에서

|\alpha| \leq |\beta|

이다.

문맥자유문법(CFG, context-free grammar). 모든 생성 규칙은

A \rightarrow \alpha

형태를 갖는다. (

A

는 하나의 비말단(nonterminal)이고,

\alpha

는

V^*

에 속하는 문자열이다.

정규문법(RG, regular grammar). 모든 생성규칙은 다음 2가지 중 하나로 표현된다:

(1) $A \rightarrow tB$ 또는 $A \rightarrow t$ , 여기서 $t \in {V_T}^*$ 이고, $A, B \in V_N$ 이다.
(2) $A \rightarrow Bt$ 또는 $A \rightarrow t$ , 여기서 $t \in {V_T}^*$ 이고, $A, B \in V_N$ 이다.

유형	문법	언어	오토마타	생성규칙	언어의 예
제 0유형	제약없는 문법	귀납적 가산 언어	튜링 기계	제약 없음	-
제 1유형	문맥의존문법	문맥의존언어	선형 구속형 비결정성 튜링 기계	αAβ → αγβ	$a^n b^n c^n$
제 2유형	문맥자유문법	문맥자유언어	비결정성 푸시다운 오토마타	A → γ	$a^n b^n$
제 3유형	정규문법	정규언어	유한 상태 기계	A → aB A → a	$a^n$

Noam Chomsky: Three models for the description of language, IRE Transactions on Information Theory, 2 (1956), pages 113-124
Noam Chomsky: On certain formal properties of grammars, Information and Control, 1 (1959), pages 91-112

Gourt Home::Gourt :: 촘스키 위계