촘스키 위계 문서 원본 보기

{{위키데이터 속성 추적}}
'''촘스키 위계'''(Chomsky hierarchy)는 [[형식 언어]]를 생성하는 [[형식 문법]]의 클래스 사이의 위계를 말한다. [[노엄 촘스키]]가 1956년에 제시하였다.

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

* 알파벳 <math>T</math>는 기호들의 [[유한 집합]]이다.
* 언어 <math>L</math>은 <math>T^*</math>의 [[부분집합]]이다.

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

<math>L_1 =</math> {ㄱㅏ, ㄴㅏ, ㄷㅏ, ㄹㅏ, ..., ㅎㅏ}

<math>L_2 =</math> {ㄱㅏㄷㅏ, ㅅㅏㄷㅏ, ㅈㅏㄷㅏ, ㅊㅏㄷㅏ, ㅌㅏㄷㅏ, ㅍㅏㄷㅏ, ㅎㅏㄷㅏ}

<math>L_3 =</math> {ㄱㄱㅏㄷㅏ, ㄷㄷㅏㄷㅏ, ㅅㅅㅏㄷㅏ, ㅈㅈㅏㄷㅏ}

== 문법 ==
{{본문|형식 문법}}

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

<math>G = (V_N, V_T, P, S)</math>
* <math>V_N</math> : 비말단 기호의 유한 집합
* <math>V_T</math> : 말단 기호의 유한 집합
* <math>P</math> : 생성규칙의 유한 집합
* <math>S</math> : <math>V_N</math>에 속하는 기호로 시작 기호 또는 문장 기호

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

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

== 위계 ==
[[파일:Chomsky-hierarchy.svg|섬네일|오른쪽|250px|촘스키 위계의 포함 관계]]
이렇게 정의된 형식문법은 생성규칙에 어떠한 제약이 있는가에 따라서 다음과 같이 나눌 수 있다.

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

=== 제1유형 문법 ===
[[문맥 의존 문법]](CSG, context-sensitive grammar)은 [[문맥 의존 언어]]를 생성한다. 생성 규칙은 <math>\alpha A\beta \rightarrow \alpha\gamma\beta</math>이며, 이들은 항상 <math>\alpha \rightarrow \beta</math>에서 <math>|\alpha| \leq |\beta|</math>이다. [[선형 구속 오토마타]]로 인식할 수 있다.

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

=== 제3유형 문법 ===
[[정규 문법]](RG, regular grammar)은 오른쪽 정규 문법과 왼쪽 정규 문법의 총칭이다. 다음은 각 생성규칙:
* (오른쪽 정규 문법) <math>A \rightarrow tB</math> 또는 <math>A \rightarrow t</math>, 여기서 <math>t \in {V_T}^*</math>이고, <math>A, B \in V_N</math>이다.
* (왼쪽 정규 문법) <math>A \rightarrow Bt</math> 또는 <math>A \rightarrow t</math>, 여기서 <math>t \in {V_T}^*</math>이고, <math>A, B \in V_N</math>이다.

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

== 형식문법의 촘스키 위계 ==
{| class="wikitable"
|- style="background: #cccccc;"
! 유형</th>
! 문법</th>
! 언어</th>
! 인식 오토마타</th>
! 생성규칙</th>
! 언어의 예</th>
|-
| 제0유형</td>
| 제약없는 문법</td>
| 귀납적 가산 언어</td>
| [[튜링 기계]]</td>
| <math>\alpha A \beta \rightarrow \beta</math></td>
| -</td>
|-
| 제1유형</td>
| 문맥의존문법</td>
| 문맥의존언어</td>
| 선형 구속형 [[비결정론적 튜링 기계]]</td>
| <math>\alpha A \beta \rightarrow \alpha \gamma \beta</math></td>
| <math>a^n b^n c^n</math></td>
|-
| 제2유형</td>
| 문맥자유문법</td>
| 문맥자유언어</td>
| 비결정론적 [[푸시다운 오토마타]]</td>
| <math>A \rightarrow \alpha</math></td>
| <math>a^n b^n</math></td>
|-
| 제3유형</td>
| 정규문법</td>
| 정규언어</td>
| [[유한 상태 기계]]</td>
| <math>A \rightarrow aB</math> <br> <math>A \rightarrow a</math></td>
| <math>a^n</math></td>
|}

== 참고 문헌 ==
* 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

{{형식언어 및 형식문법}}

{{전거 통제}}

[[분류:전산언어학]]
[[분류:노엄 촘스키]]
[[분류:1956년 컴퓨팅]]