맨위로가기

촘스키 위계

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

촘스키 위계는 형식 문법을 생성 규칙의 제약 조건에 따라 분류한 것으로, 0형부터 3형까지 4가지 유형으로 나뉜다. 촘스키 위계는 노엄 촘스키가 제안했으며, 각 유형은 서로 다른 문법, 언어, 인식 오토마톤, 생성 규칙을 가지며, 정규 언어, 문맥 자유 언어, 문맥 민감 언어, 재귀적 가산 언어 순으로 포함 관계를 형성한다.

더 읽어볼만한 페이지

  • 1956년 컴퓨팅 - 다트머스 회의
    다트머스 회의는 1956년 다트머스 대학교에서 열린 인공지능 연구를 위한 최초의 회의로, 존 매카시, 마빈 민스키 등이 참여하여 "인공지능"이라는 용어를 처음 사용하고 지능의 모든 측면을 기계로 시뮬레이션할 수 있다는 아이디어를 제시하며 인공지능 연구의 초석을 다졌다.
  • 1956년 컴퓨팅 - P-NP 문제
    P-NP 문제는 계산 복잡도 이론에서 P와 NP 복잡도 종류의 관계에 대한 미해결 문제로, 컴퓨터 과학과 수학에 혁명적인 변화를 가져올 것으로 예상되며 암호학, 최적화, 인공지능 등 다양한 분야에 큰 영향을 미칠 수 있다.
  • 노엄 촘스키 - 선전 모델
    선전 모델은 미디어가 권력 구조의 영향으로 특정 메시지를 전달하고 여론을 조작하는 방식을 설명하는 이론으로, 다섯 가지 필터를 통해 미디어 콘텐츠가 기업 이익을 선호하는 방향으로 편향된다고 주장하지만, 미디어의 다양성과 기업 부패 보도 사례 등 비판도 존재한다.
  • 노엄 촘스키 - 생성문법
    생성문법은 자연언어의 문법성을 판단하고 문장을 생성하는 규칙을 다루는 언어학적 접근 방식으로, 인간의 문법적 지식 모델 구축을 통해 언어의 인지적 기초를 탐구하며, 촘스키는 인간이 보편 문법을 생득적으로 갖추고 있다고 보았다.
  • 전산언어학 - 알고리즘
    알고리즘은 문제 해결을 위한 명확하고 순서화된 유한 개의 규칙 집합으로, 알콰리즈미의 이름에서 유래되었으며, 수학 문제 해결 절차로 사용되다가 컴퓨터 과학에서 중요한 역할을 하며 다양한 방식으로 표현되고 효율성 분석을 통해 평가된다.
  • 전산언어학 - 단어 의미 중의성 해소
    단어 의미 중의성 해소(WSD)는 문맥 내 단어의 의미를 파악하는 계산 언어학 과제로, 다양한 접근 방식과 외부 지식 소스를 활용하여 연구되고 있으며, 다국어 및 교차 언어 WSD 등으로 발전하며 국제 경연 대회를 통해 평가된다.
촘스키 위계
촘스키 위계
촘스키 위계 다이어그램
촘스키 위계 다이어그램 (화살표 방향은 포함 관계를 나타냄)
분류
문법 0 형식제한 없는 문법
문법 1 형식문맥 의존 문법
문법 2 형식문맥 자유 문법
문법 3 형식정규 문법
대응 오토마타
문법 0 형식튜링 기계
문법 1 형식선형 유계 오토마타
문법 2 형식푸시다운 오토마타
문법 3 형식유한 상태 오토마타
생성 규칙
문법 0 형식α → β (α, β는 비단말기호와 단말기호의 임의의 문자열, α는 적어도 하나의 비단말기호를 포함)
문법 1 형식αAβ → αγβ (A는 비단말기호, α, β, γ는 비단말기호와 단말기호의 문자열, γ는 공 문자열이 될 수 없음)
문법 2 형식A → γ (A는 비단말기호, γ는 비단말기호와 단말기호의 문자열)
문법 3 형식A → a 또는 A → aB 또는 A → Ba (A, B는 비단말기호, a는 단말기호)
언어
문법 0 형식재귀 열거 가능 언어
문법 1 형식문맥 의존 언어
문법 2 형식문맥 자유 언어
문법 3 형식정규 언어
최소 요구 사항
문법 0 형식없음
문법 1 형식문법이 비어 있지 않아야 함
문법 2 형식문법이 촘스키 정규형이어야 함
문법 3 형식문법이 정규 문법이어야 함
폐쇄성
문법 0 형식모든 연산에 대해 닫혀 있음
문법 1 형식합집합, 교집합, 연결, 여집합, 클린 스타에 대해 닫혀 있음
문법 2 형식합집합, 연결, 클린 스타에 대해 닫혀 있음
문법 3 형식합집합, 교집합, 차집합, 연결, 여집합, 클린 스타에 대해 닫혀 있음
결정 가능성
문법 0 형식대부분의 문제는 결정 불가능
문법 1 형식선형 시간
문법 2 형식O(n^3)
문법 3 형식O(n)

2. 형식 언어

형식 언어는 기호들의 집합(알파벳)을 이용하여 만들어지는 문자열들의 집합이다.

2. 1. 정의

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

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

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

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

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

2. 2. 예시

한국어의 자음과 모음을 알파벳으로 하는 경우, 다음과 같은 형식 언어들을 정의할 수 있다.

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

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

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

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

3. 형식 문법

형식 문법은 형식 언어를 생성하는 규칙들의 집합이다. 형식 문법은 종결 기호(형식 언어의 단어에 사용되는 문자), 비종결 기호의 유한 집합, 생성 규칙 (각 생성 규칙은 오른쪽과 왼쪽에 기호열로 구성된 단어를 포함), 시작 기호로 구성된다.

3. 1. 정의

형식 문법은 기호들의 집합에 그 기호들로부터 문장을 만드는 규칙이 부여된 것으로 정의될 수 있다. 형식 문법(G)은 다음과 같이 네 가지 요소로 구성된다.

:1. V_N : 비종결 기호의 유한 집합

:2. V_T : 종결 기호(''terminal symbol'')의 유한 집합 (형식 언어의 단어에 사용되는 문자)

:3. P : 생성 규칙(''production rule'')의 유한 집합 (각 생성 규칙은 오른쪽과 왼쪽에 기호열로 구성된 단어를 포함)

:4. S : V_N에 속하는 기호로 시작 기호(''start symbol'') 또는 문장 기호

생성 규칙은 어떤 단어에 적용되어 규칙의 왼쪽에 있는 단어를 오른쪽에 있는 기호열로 치환한다. 유도는 일련의 규칙 적용 과정이다. 이러한 문법으로 시작 기호에서 시작하여 생성 규칙을 적용해 나가면 종결 기호만으로 구성된 단어를 생성한다. 그러한 단어 전체의 집합이 형식 언어이다.

비종결 기호는 대문자, 종결 기호는 소문자로 표시되는 경우가 많고, 시작 기호는 S로 표시된다. 예를 들어, 종결 기호 \{a, b\} 와 비종결 기호 \{S, A, B\}로 구성된 문법의 생성 규칙이 다음과 같다고 가정한다.

  • S \rightarrow ABS
  • S \rightarrow \epsilon (여기서 \epsilon는 빈 문자열)
  • BA \rightarrow AB
  • BS \rightarrow b
  • Bb \rightarrow bb
  • Ab \rightarrow ab
  • Aa \rightarrow aa

이것으로 시작 기호 S에서 정의되는 모든 단어로 구성된 언어는 a^{n} b^{n}이다(n개의 a 다음에 n개의 b가 이어지는 형식). 비슷한 언어를 더 간단한 문법으로 정의한 예시는 다음과 같다. 종결 기호 \{p, q\}, 비종결 기호 \{S\}, 시작 기호 S에서 생성 규칙은 다음과 같다.

:S \rightarrow pSq

:S \rightarrow \epsilon

3. 2. 표기법

형식 문법을 기술할 때 사용되는 일반적인 표기법은 다음과 같다.[1]

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


비종결 기호는 대문자, 종결 기호는 소문자로 표시되는 경우가 많고, 시작 기호는 S로 표시된다.[2]

4. 촘스키 위계

촘스키 위계는 형식 문법을 생성 규칙의 제약 조건에 따라 분류한 것이다. 노엄 촘스키가 제안했으며, 마르셀-폴 슈츠엔베르거도 형식 언어 이론 발전에 기여했다.[1]

촘스키 위계의 포함 관계


형식 문법은 생성 규칙에 어떠한 제약이 있는지에 따라 분류할 수 있다. 촘스키는 변형 생성 문법을 공식화하는 과정에서 "언어 묘사를 위한 세 가지 모델"을 통해 촘스키 위계에 대한 일반적인 아이디어를 처음 제시했다.

언어학자들과는 별개로, 수학자들은 계산 모델(오토마타)을 개발하고 있었다. 언어에서 문장을 구문 분석하는 것은 계산과 유사하며, 촘스키가 설명한 문법은 다양한 기계 모델과 계산 능력이 유사하고 동등하다는 것이 밝혀졌다.[2]

촘스키 위계의 각 문법 유형, 생성되는 언어, 인식하는 오토마톤, 규칙 형식은 다음과 같다.

문법언어인식 오토마톤생성 규칙 (제약 조건)예시[3][4]
3형 문법정규 언어유한 상태 오토마톤L = \{a^n>n > 0\}
2형 문법문맥 자유 언어비결정적 푸시다운 오토마톤A \rightarrow \alphaL = \{a^nb^n>n > 0\}
1형 문법문맥 민감 언어선형 유계 비결정적 튜링 기계\alpha A \beta \rightarrow \alpha \gamma \betaL = \{a^nb^nc^n>n > 0\}
0형 문법재귀적 가산 언어튜링 기계\gamma \rightarrow \alpha (\gamma는 비어 있지 않음)L = \{w>w는 종료하는 튜링 기계를 설명한다\}



재귀 언어에 해당하는 문법 집합은 이 위계에 포함되지 않으며, 0형과 1형 사이에 위치한다.

모든 정규 언어는 문맥 자유 언어이고, 모든 문맥 자유 언어는 문맥 민감 언어이며, 모든 문맥 민감 언어는 재귀 언어이고, 모든 재귀 언어는 재귀적 가산 언어이다. 이들은 모두 올바른 포함 관계를 가지며, 이는 문맥 민감 언어가 아닌 재귀적 가산 언어, 문맥 자유 언어가 아닌 문맥 민감 언어, 정규 언어가 아닌 문맥 자유 언어가 존재한다는 것을 의미한다.[5]

4. 1. 개요

촘스키 위계는 형식 문법을 4가지 유형으로 분류하며, 각 유형은 특정 종류의 언어를 생성하고, 특정 오토마타에 의해 인식된다.[1]

언어학자들과 별개로, 수학자들은 계산 모델(오토마타)을 개발하고 있었다. 언어에서 문장을 구문 분석하는 것은 계산과 유사하며, 촘스키가 설명한 문법은 다양한 기계 모델과 계산 능력이 유사하고 동등하다는 것이 밝혀졌다.[2]

다음 표는 촘스키 위계의 각 문법 유형, 생성되는 언어 클래스, 이를 인식하는 오토마톤 유형, 규칙의 형식을 요약한 것이다.

문법언어인식 오토마톤생성 규칙 (제약 조건)예시[3][4]
3형 문법정규 언어유한 상태 오토마톤L = \{a^n>n > 0\}
2형 문법문맥 자유 언어비결정적 푸시다운 오토마톤A \rightarrow \alphaL = \{a^nb^n>n > 0\}
1형 문법문맥 민감 언어선형 유계 비결정적 튜링 기계\alpha A \beta \rightarrow \alpha \gamma \betaL = \{a^nb^nc^n>n > 0\}
0형 문법재귀적 가산 언어튜링 기계\gamma \rightarrow \alpha (\gamma는 비어 있지 않음)L = \{w>w는 종료하는 튜링 기계를 설명한다\}



모든 정규 언어는 문맥 자유 언어이고, 모든 문맥 자유 언어는 문맥 민감 언어이며, 모든 문맥 민감 언어는 재귀 언어이고, 모든 재귀 언어는 재귀적 가산 언어이다. 이들은 모두 올바른 포함 관계를 가지며, 이는 문맥 민감 언어가 아닌 재귀적 가산 언어, 문맥 자유 언어가 아닌 문맥 민감 언어, 정규 언어가 아닌 문맥 자유 언어가 존재한다는 것을 의미한다.[5]

4. 2. 각 유형별 특징



촘스키 위계는 형식 문법의 생성 규칙에 따라 제0유형부터 제3유형까지 4가지 유형으로 분류된다. 각 유형은 특정 종류의 언어를 생성하며, 이를 인식하는 오토마타(자동 기계)가 존재한다.

유형문법언어인식 오토마타생성 규칙예시
제0유형제약 없는 문법귀납적 가산 언어튜링 기계\alpha \rightarrow \beta (단, \alpha는 비어 있지 않음)-
제1유형문맥 의존 문법문맥 의존 언어선형 구속형 비결정론적 튜링 기계\alpha A\beta \rightarrow \alpha\gamma\betaa^n b^n c^n
제2유형문맥 자유 문법문맥 자유 언어비결정론적 푸시다운 오토마타A \rightarrow \alphaa^n b^n
제3유형정규 문법정규 언어유한 상태 오토마타A \rightarrow aB 또는 A \rightarrow a (우선 정규)
A \rightarrow Ba 또는 A \rightarrow a (좌선 정규)
a^n


  • 모든 정규 언어는 문맥 자유 언어에 포함되고, 모든 문맥 자유 언어는 문맥 의존 언어에 포함되며, 모든 문맥 의존 언어는 귀납적 가산 언어에 포함된다.
  • 각 유형은 상위 유형의 진부분집합이다. 즉, 문맥 의존 언어가 아닌 귀납적 가산 언어, 문맥 자유 언어가 아닌 문맥 의존 언어, 정규 언어가 아닌 문맥 자유 언어가 존재한다.[5]

4. 2. 1. 제0유형 문법 (무제약 문법)

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

0형 문법은 튜링 기계에 의해 인식될 수 있는 모든 언어를 정확히 생성하므로, 생성될 수 있는 모든 언어는 0형 문법으로 생성될 수 있다.

문법언어인식 오토마톤생성 규칙 (제약 조건)예시
0형 문법재귀적 가산 언어튜링 기계\gamma \rightarrow \alpha (\gamma는 비어 있지 않음)L = \{w>w는 종료하는 튜링 기계를 설명한다\}


4. 2. 2. 제1유형 문법 (문맥 의존 문법)

1형 문법(문맥 의존 문법)은 문맥 의존 언어를 생성한다. 이러한 문법은 \alpha A\beta \rightarrow \alpha\gamma\beta 형태의 규칙을 가지며, 여기서 A는 비단말 기호이고, \alpha, \beta\gamma는 단말 기호 및/또는 비단말 기호의 문자열이다. 문자열 \alpha\beta는 비어 있을 수 있지만, \gamma는 비어 있지 않아야 한다. 규칙 S \rightarrow \epsilonS가 어떤 규칙의 오른쪽에도 나타나지 않는 경우 허용된다.[3][4] 이러한 문법에 의해 설명되는 언어는 정확히 선형 유계 오토마톤 (입력의 길이의 상수 배로 테이프가 제한된 비결정론적 튜링 기계)에 의해 인식될 수 있는 모든 언어이다.

예를 들어, 문맥 의존 언어 L = \{a^nb^nc^n|n > 0\}은 1형 문법 G = (\{S,A,B,C,W,Z\}, \{a, b\}, P, S)에 의해 생성되며, 여기서 생성 규칙 P는 다음과 같다.

:S → aBC

:S → aSBC

:CB → CZ

:CZ → WZ

:WZ → WC

:WC → BC

:aB → ab

:bB → bb

:bC → bc

:cC → cc

이 언어는 문맥 의존적이지만, 문맥 자유 언어에 대한 펌핑 보조 정리에 의해 문맥 자유적이지 않다. 이 문법이 L = \{a^nb^nc^n|n > 0\}을 생성한다는 증명은 문맥 의존 문법에 대한 문서에서 간략하게 설명되어 있다.

4. 2. 3. 제2유형 문법 (문맥 자유 문법)

문맥 자유 문법(CFG, context-free grammar)은 문맥 자유 언어를 생성한다. 모든 생성 규칙은 A \rightarrow \alpha 형태를 갖는다. (A는 하나의 비말단(nonterminal)이고, \alpha는 단말 기호 및/또는 비말단 기호들의 문자열이다.) 푸시다운 오토마타로 인식할 수 있다.

문맥 자유 언어, 또는 결정적 문맥 자유 언어의 하위 집합은 대부분의 프로그래밍 언어의 구문 구조에 대한 이론적 기반을 형성하지만, 선언 및 범위로 인해 구문에는 문맥 의존적인 이름 확인도 포함된다.[7] 종종 LL 파서와 같이 구문 분석을 더 쉽게 만들기 위해 문법의 하위 집합이 사용된다.

예를 들어, 문맥 자유 언어 L = \{a^nb^n|n > 0\}는 2형 문법 G = (\{S\}, \{a, b\}, P, S)에 의해 생성되며, 여기서 프로덕션 P는 다음과 같다.

  • S → aSb
  • S → ab


이 언어는 정규 언어에 대한 펌핑 보조 정리에 의해 정규적이지 않지만, 문맥 자유적이다.

4. 2. 4. 제3유형 문법 (정규 문법)

정규 문법(RG, regular grammar)은 오른쪽 정규 문법과 왼쪽 정규 문법을 통틀어 말한다.

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


이것으로 모든 정규 언어를 표현할 수 있으며, 정규 표현식과 같기 때문에 유한 상태 기계가 인식할 수 있다.[3][4]

3형 문법은 정규 언어를 생성한다. 이러한 문법은 규칙을 왼쪽 변수에 하나의 비단말 기호로 제한하고, 오른쪽 변수는 단일 단말 기호로 구성하며, 선택적으로 단일 비단말 기호가 뒤따른다. 이 경우 문법은 "오른쪽 정규"이다. 또는 모든 규칙의 오른쪽 변수는 단일 단말 기호로 구성될 수 있으며, 선택적으로 단일 비단말 기호가 "앞에 올" 수 있다("왼쪽 정규"). 이들은 동일한 언어를 생성한다. 그러나 왼쪽 정규 규칙과 오른쪽 정규 규칙을 결합하면 언어가 더 이상 정규 언어가 아닐 수 있다. 규칙 S \rightarrow \varepsilonS가 어떤 규칙의 오른쪽에도 나타나지 않는 경우에도 허용된다.

이러한 언어는 정확히 유한 상태 자동기계에 의해 결정될 수 있는 모든 언어이다. 또한, 이 형식 언어군은 정규 표현식으로 얻을 수 있다. 정규 언어는 일반적으로 검색 패턴과 프로그래밍 언어의 어휘 구조를 정의하는 데 사용된다.

예를 들어, 정규 언어 L = \{a^n|n > 0\}는 다음 생성 규칙 P를 가진 3형 문법 G = (\{S\}, \{a, b\}, P, S)에 의해 생성된다.

문법언어인식 오토마톤생성 규칙 (제약 조건)예시
3형 문법정규 언어유한 상태 오토마톤L = \{a^n>n > 0\}


참조

[1] 서적 A Companion to Chomsky https://www.research[...] 2021-04-27
[2] 서적 Automata and computability https://books.google[...] Springer
[3] 웹사이트 Applications, Chomsky hierarchy, and Recap https://www.cs.ru.nl[...] 2016
[4] 서적 Languages and machines: An Introduction to the Theory of Computer Science Addison Wesley Longman 1997
[5] 서적 Handbook of Mathematical Psychology John Wiley and Sons, Inc.
[6] 서적 Introduction to the Theory of Computation https://archive.org/[...] Cengage Learning
[7] 문서 たとえばC言語の場合の1例としては、typedefが現れた後は同じ綴りが単なる識別子から型名に変化するため、厳密には文脈自由文法で完全には扱えない。



본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com