촘스키 계층

형식 언어 이론, 컴퓨터 과학, 언어학에서 촘스키 계층(^[1]촘스키-슐첸버거 계층이라고도 함)은 형식 문법 클래스의 억제 계층이다.

이 문법 계층은 1956년 ^[2]노암 촘스키에 의해 기술되었다.그것은 또한 공식 언어 이론의 발전에 중요한 역할을 한 마르셀-폴 쉬첸버거의 이름을 따서 붙여졌다.

형식 문법

이 유형의 형식 문법은 유한한 생산 규칙 집합(왼쪽 → 오른쪽)으로 구성되며, 여기서 각 문법은 다음과 같은 기호의 유한한 시퀀스로 구성됩니다.

• 유한한 비말단 기호 세트(일부 생산 규칙이 아직 적용될 수 있음을 나타냄)
• 유한한 종단 기호 세트(생산 규칙을 적용할 수 없음을 나타냄)
• 시작 기호(단말기 이외의 구별 기호)

형식 문법은 형식 언어를 위한 공리 스키마를 제공(또는 생성)하며, 형식 언어는 (보통 무한) 다른 기호 시퀀스에 생성 규칙을 적용하여 구성될 수 있는 유한 길이의 기호 시퀀스의 집합입니다(처음에는 시작 기호만 포함).규칙은 왼쪽에 있는 기호를 오른쪽에 나타나는 기호로 대체함으로써 적용할 수 있다.규칙 적용 시퀀스를 파생이라고 합니다.이러한 문법은 형식 언어를 정의한다: 모든 단어는 시작 기호에서 파생하여 도달할 수 있는 종단 기호로만 구성된다.

대부분의 경우 비종단은 대문자, 끝은 소문자로, 시작 기호는 S로 표시됩니다.예를 들어 터미널이 {a, b}인 문법, 터미널이 아닌 {S, A, B}인 생산 규칙

S → AB

S → " (여기서 "는 빈 문자열)

A → aS

B → b

및 시작 기호 S는 ${\displaystyle a^{}}$ ${\displaystyle {}^{}{}^{}}$ ${\displaystyle b^{}}$n \ $displaystyle$ a$^{n} b^{n}$ 형식의 $모든{\displaystyle {}^{}}$ 단어의 언어를 정의합니다(즉, a의 복사본 n개, b의 복사본 n개).

같은 언어를 정의하는 간단한 문법은 다음과 같습니다.

터미널 {a, b}, 비터미널 {S}, 시작 기호 S, 운영 규칙

S → aSb

S → ε

또 다른 예로 영어 완구 하위 집합의 문법은 다음과 같다.

터미널

{generate, 밉다, great, green, idea, languists}

비종단

{S, NP, VP, N, V, Adj}

생산 규칙

S → NP VP

NP → Adj NP

NP → N

VP → V NP

VP → V

N → 아이디어

N → 언어학자

V → 생성

V → 증오

Adj → 대단합니다.

Adj → 녹색

기호 S를 시작합니다.파생 예는 다음과 같습니다.

S → NP VP → Adj N VP → Adj N V NP → Adj N V Adj NP → Adj N → Adj N V Adj N → Adj N → Adj N → Adj N adj N → Adj N adj N → Adj N ad N

이 문법에서 파생될 수 있는 다른 시퀀스로는 "이념은 위대한 언어학자를 증오한다"와 "이념은 생성된다"가 있다.이 문장들은 무의미하지만 구문적으로는 정확하다.구문적으로 잘못된 문장(예: "아이디어s great hate")은 이 문법에서 파생될 수 없습니다.1957년 촘스키가 제시한 유사한 예에 대해서는 "색채가 없는 녹색 아이디어가 맹렬히 잠든다"를 참조한다. 보다 자연스러운 언어 예시와 그 영역의 형식 문법의 문제에 대해서는 구 구조 문법과 구 구조 규칙을 참조한다.

계층

다음 표는 촘스키의 네 가지 종류의 문법, 그것이 만들어내는 언어의 종류, 그것을 인식하는 자동화의 종류, 그리고 그 규칙이 가져야 할 형태를 요약한 것이다.

문법.	언어들	오토마톤	생산 규칙(제약)*	예[3]
타입 0	재귀적 열거 가능	튜링 기계	$\displaystyle \rightarrow \alpha }$ (제한 없음)	$L$ ${\displaystyle =}$ { ${\displaystyle w}${ $displaystyle$ L = \ { $w$}는$$ 종단 튜링 기계를 나타냅니다$.$ { $display$ \$$}
타입 1	문맥 의존형	선형 유계 비결정적 튜링 기계	$\displaystyle \alpha A\beta \오른쪽 화살표 \alpha \gamma \beta }$	$\displaystyle L=\{a^{n}b^{n}c^{n}n>0\}$
타입 2	콘텍스트 프리	비결정론적 푸시다운 오토마톤	${\style A\오른쪽 화살표\alpha} 표시$	$\displaystyle L=\{a^{n}b^{n}n>0\}$
타입 3	규칙적인.	유한 상태 오토마톤	$(*style A\오른쪽 화살표\text{a})$ 그리고. $(*style A\오른쪽 화살표\text{a})B}$	${\displaystyle L=\{a^{n} n\geq 0\}$
* 기호의 의미: $displaystyle =$ $단말기$ ${\displaystyle }$$A{\displaystyle }$$(\displaystyle$ A$),$ B$(\displaystyle$ B$)$ =$$ 비단말기 ${\displaystyle }$$\alpha {\displaystyle }$$(\displaystyle \alpha$ $\}$ ,$\beta {\displaystyle }$(\$displaystyle$ \displaystyle$)$ , β(\displaystyle \$displays })$ =$$ 단말기 문자열 및/또는 비표준 ${\displaystyle \mathrm{문자열}}$ ${\displaystyle }$α$(\displaystyle \alpha$$\beta {\displaystyle }$(\$displaystyle$ \$display }) =$ 비어 있을 수 ${\displaystyle \mathrm{있음}}$) $\displaystyle$ \displays$$= 비어있지 ${\displaystyle \mathrm{않음}}$

재귀 언어에 대응하는 문법 세트는 이 계층의 멤버가 아닙니다.이러한 문법은 Type-0과 Type-1 사이에 있습니다.

모든 정규언어는 문맥에 구애받지 않고, 모든 문맥에 구애받지 않는 언어는 문맥에 구애받지 않고, 모든 문맥에 구애받지 않는 언어는 재귀적으로 열거됩니다.이것들은 모두 적절한 포함입니다.즉, 컨텍스트에 의존하지 않고 컨텍스트에 의존하지 않는 반복 열거형 언어가 존재하며 컨텍스트에 의존하지 않는 언어도 정규적이지 않은 ^[4]컨텍스트에 의존하지 않는 언어도 존재합니다.

타입 0 문법

이 섹션은 Wikipedia의 품질 기준을 충족하기 위해 청소가 필요할 수 있습니다.구체적인 문제는 이 모든 "유형" 섹션이 예시로부터 혜택을 받을 수 있다는 것입니다. 가능하다면 이 섹션의 개선에 협조해 주십시오.(2022년 6월) (이 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다)

Type-0 문법은 모든 형식 문법을 포함합니다.튜링 기계로 인식할 수 있는 모든 언어를 생성합니다.이 언어들은 재귀적으로 열거할 수 있는 언어 또는 ^[5]튜링 인식 가능한 언어라고도 합니다.이것은 항상 정지하는 튜링 머신에 의해 결정되는 재귀 언어와는 다르다는 점에 유의하십시오.

제1종 문법

유형 1 문법은 상황에 맞는 언어를 생성합니다.${\displaystyle \mathrm{이러한}}$ 문법은 $A를$$$비단말기, $A$를$$비단말기,$$β$(\$$displaystyle$$\alpha \beta \rightarrow \alpha$ \alpha$},$$$$\beta {\displaystyle }$(\$displaystyle \alpha$$\}),$ $\beta {\displaystyle }$(\$displaystyle$ \alpha $})$ 문자열$$$$ 및$$비단말기어(\displaystyle $\al$) $형식$의 규칙을 가지고 있습니다.$(\displaystyle \alpha})$ $및$ β(\$displaystyle \beta)$는 비워 둘 수 있지만$,$ "\$displaystyle \gamma"$는 비워 둘 수 없습니다.${\displaystyle S}$ $→$ ${\$ { $display$ style S \ $rightarrow$\ $silon }$ 규칙은$$ S { $display style$ S$$}가$$ 규칙의 오른쪽에 나타나지 $않으면{\displaystyle }$ 허용됩니다.이 문법들에 의해 기술된 언어들은 선형 유계 오토마톤(테이프가 입력 길이의 일정한 곱에 의해 경계가 되는 비결정론적 튜링 기계)에 의해 인식될 수 있는 정확히 모든 언어들이다.

제2종 문법

타입 2의 문법은 문맥이 없는 언어를 생성합니다.A ${\displaystyle \to }$ {\$displaystyle$ A$\rightarrow \alpha}$ $형식$의 규칙에 의해 정의되며$,$ $A{\displaystyle }$$${\$displaystyle$ A$}$는 비단말기, α {\displaystyle $\alpha}$는 비단말기 문자열 및/또는 비단말기 문자열입니다.이들 언어는 비결정론적 푸시다운 자동화에 의해 인식될 수 있는 모든 언어입니다.문맥이 없는 언어(또는 결정론적 문맥이 없는 언어의 서브셋)는 대부분의 프로그래밍 언어의 구문 구조의 이론적 기초가 되지만, 그 구문에는 선언과 범위에 따른 문맥에 민감한 이름 해결도 포함됩니다.LL 파서와 같이 구문 분석을 쉽게 하기 위해 문법 서브셋이 사용되는 경우가 많습니다.

제3종 문법

타입 3의 문법은 정규 언어를 생성합니다.이러한 문법은 규칙을 왼쪽의 단일 비단말기와 오른쪽의 단일 단말기로 제한하며, 그 뒤에 단일 비단말기(오른쪽 정규)가 이어지는 경우가 있습니다.또는 문법의 오른쪽은 단일 단말기로 구성될 수 있으며, 그 앞에 단일 비단말기(왼쪽 정규)가 있을 수 있습니다.이들은 같은 언어를 생성합니다.하지만, 만약 좌파 규칙과 우파 규칙들이 결합된다면, 그 언어는 더 이상 규칙적일 필요가 없다.$규칙{\displaystyle }$ S$$${\displaystyle \to }$ ${\displaystyle \epsilon }$ { $display$ style$$$$S \ $rightarrow$\ $varepsilon }$는 S { displaystyle S$}$가 규칙의 S →$$ε { $displaystyle$ S \ varepsilon }이 언어들은 정확히 유한 상태 자동화에 의해 결정될 수 있는 모든 언어들이다.또한 정규 표현으로 이 정식 언어 패밀리를 얻을 수 있습니다.정규 언어는 일반적으로 검색 패턴과 프로그래밍 언어의 어휘 구조를 정의하는 데 사용됩니다.

레퍼런스

• Chomsky, Noam (1959). "On certain formal properties of grammars" (PDF). Information and Control. 2 (2): 137–167. doi:10.1016/S0019-9958(59)90362-6.
• Chomsky, Noam; Schützenberger, Marcel P. (1963). "The algebraic theory of context free languages". In Braffort, P.; Hirschberg, D. (eds.). Computer Programming and Formal Systems (PDF). Amsterdam: North Holland. pp. 118–161.
• Davis, Martin D.; Sigal, Ron; Weyuker, Elaine J. (1994). Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science (2nd ed.). Boston: Academic Press, Harcourt, Brace. p. 327. ISBN 0-12-206382-1.