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

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

• 알파벳 ${\displaystyle T}$는 기호들의 유한 집합이다.
• 언어 ${\displaystyle L}$은 ${\displaystyle T^{*}}$의 부분집합이다.

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

${\displaystyle L_{1}=}$ {ㄱㅏ, ㄴㅏ, ㄷㅏ, ㄹㅏ, ..., ㅎㅏ}

${\displaystyle L_{2}=}$ {ㄱㅏㄷㅏ, ㅅㅏㄷㅏ, ㅈㅏㄷㅏ, ㅊㅏㄷㅏ, ㅌㅏㄷㅏ, ㅍㅏㄷㅏ, ㅎㅏㄷㅏ}

${\displaystyle L_{3}=}$ {ㄱㄱㅏㄷㅏ, ㄷㄷㅏㄷㅏ, ㅅㅅㅏㄷㅏ, ㅈㅈㅏㄷㅏ}

 이 부분의 본문은 형식 문법입니다.

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

${\displaystyle G=(V_{N},V_{T},P,S)}$

• ${\displaystyle V_{N}}$ : 비말단 기호의 유한 집합
• ${\displaystyle V_{T}}$ : 말단 기호의 유한 집합
• ${\displaystyle P}$ : 생성규칙의 유한 집합
• ${\displaystyle S}$ : ${\displaystyle V_{N}}$에 속하는 기호로 시작 기호 또는 문장 기호

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

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

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

무제약 문법(UG, unrestricted grammar)은 생성규칙(production rule)에 아무런 제약을 두지 않으나, 좌변이 공집합이 되는 경우만은 없다(즉 ${\displaystyle \alpha \rightarrow \beta }$에서 ${\displaystyle \alpha \neq \epsilon }$). 이들은 모든 종류의 형식 문법을 포함한다. 이는 튜링 기계가 인식가능한 모든 언어를 생성하는데, 이를 재귀적 열거 가능 언어(recursively enumerable set)라 한다.

문맥 의존 문법(CSG, context-sensitive grammar)은 문맥 의존 언어를 생성한다. 생성 규칙은 ${\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }$이며, 이들은 항상 ${\displaystyle \alpha \rightarrow \beta }$에서 ${\displaystyle |\alpha |\leq |\beta |}$이다. 선형 구속 오토마타로 인식할 수 있다.

문맥 자유 문법(CFG, context-free grammar)은 문맥 자유 언어를 생성한다. 모든 생성 규칙은 ${\displaystyle A\rightarrow \alpha }$형태를 갖는다. (${\displaystyle A}$는 하나의 비말단(nonterminal)이고, ${\displaystyle \alpha }$는 ${\displaystyle V^{*}}$에 속하는 문자열.) 푸시다운 오토마타로 인식할 수 있다.

정규 문법(RG, regular grammar)은 오른쪽 정규 문법과 왼쪽 정규 문법의 총칭이다. 다음은 각 생성규칙:

• (오른쪽 정규 문법) ${\displaystyle A\rightarrow tB}$ 또는 ${\displaystyle A\rightarrow t}$, 여기서 ${\displaystyle t\in {V_{T}}^{*}}$이고, ${\displaystyle A,B\in V_{N}}$이다.
• (왼쪽 정규 문법) ${\displaystyle A\rightarrow Bt}$ 또는 ${\displaystyle A\rightarrow t}$, 여기서 ${\displaystyle t\in {V_{T}}^{*}}$이고, ${\displaystyle A,B\in V_{N}}$이다.

이로부터 모든 정규 언어를 기술할 수 있으며, 정규 표현식과 등가이기에 유한 상태 기계가 인식할 수 있다.

유형	문법	언어	인식 오토마타	생성규칙	언어의 예
제0유형	제약없는 문법	귀납적 가산 언어	튜링 기계	${\displaystyle \alpha A\beta \rightarrow \beta }$	-
제1유형	문맥의존문법	문맥의존언어	선형 구속형 비결정론적 튜링 기계	${\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }$	${\displaystyle a^{n}b^{n}c^{n}}$
제2유형	문맥자유문법	문맥자유언어	비결정론적 푸시다운 오토마타	${\displaystyle A\rightarrow \alpha }$	${\displaystyle a^{n}b^{n}}$
제3유형	정규문법	정규언어	유한 상태 기계	${\displaystyle A\rightarrow aB}$ ${\displaystyle A\rightarrow a}$	${\displaystyle 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