Chomsky hierarchy or Chomsky-Schützenberger hierarchy

aka 촘스키_계층

여기서 그렇게 번역하지 않은 이유는 계층 하면 stratum, level, layer 같은 평평한 이미지가 있어서. 계층"들"이나 계층체계나 계층구조라면 괜찮지만. 2021-12-02

hierarchy(

hierarchy

hierarchy )에는 분명히 '수직적' 구조가 존재한다.

형식언어,formal_language를 생성하는 형식문법,formal_grammar을 분류해 놓은 계층구조.

//from planetmath
형식문법,formal_grammar을 네 가지 type으로 분류하는 방법. 숫자가 작을수록 더 일반적.

//from wpko and wpen; chk.

유형	문법,grammar			언어,language	인식 오토마톤(자동기계,automaton)	생성규칙,production_rule	언어의 예
제0유형	제약 없는 문법, 무제약 문법	unrestricted grammar	UG	귀납적 가산 언어 recursively enumerable language	Turing_machine	$\alpha A \beta\to \beta$	-
제1유형	문맥의존문법	context-sensitive grammar	CSG	문맥의존언어 context-sensitive language	선형 구속형 비결정론적 튜링 기계 linear-bounded non-deterministic Turing machine	$\alpha A \beta \to \alpha \gamma \beta$	$a^nb^nc^n$
제2유형	문맥자유문법	context-free grammar	CFG	문맥자유언어 context-free language	비결정론적 푸시다운 오토마톤 non-deterministic pushdown automaton	$A\to\alpha$	$a^nb^n$
제3유형	정규문법	regular grammar	RG	정규언어 regular language	유한상태기계 finite state automaton	$A\to aB$ $A\to a$	$a^n$

문법/언어는 위로 갈수록 더 universal?
자동기계,automaton는 위로 갈수록 더 powerful?

recursively_enumerable_language
// recursively enumerable language는 한국어 번역이... 일단

재귀_열거_언어에 따르면.... 도대체 pagename을 뭐로 해야할지?

재귀 열거 언어
순환 열거 언어 (에서 넘어옴)
재귀적 열거 가능 언어
귀납적 가산 언어
부분 결정성 언어
튜링 수리성 언어

문맥의존언어,context-sensitive_language,CSL
문맥자유언어,context-free_language,CFL
정규언어,regular_language

tmp ref https://gusdnd852.tistory.com/306 chk
{

문법,grammar column만
3 정규문법 regular_grammar

정규식,regular_expression,regexp?

2 문맥자유문법,context-free_grammar,CFG

AKA 문맥무관문법??
4-tuple (v,t,p,s)로 정의

v : voca non terminal = 비 단말기호 집합 : 유한개의 원소를 가짐

문자열 만들 때 중간과정으로 쓰임
보통 대문자로 표기?
다른 기호로 유도 가능 (유도: 규칙을 한 번 써서 변환하는 것)
언어에서 직접 쓰이는 기호보다는 그들을 포괄하는 개념들이 비단말임 (??)

t : terminal voca = 단말 기호 집합 : 유한개의 원소를 가짐

위의 비단말기호와는 서로소(disjoint)
단말기호는 다른 기호로의 유도가 불가능 (단말이라는 의미)
언어에서 직접 쓰이는 기호,symbol : 알파벳,alphabet, 숫자,digit, 연산자,operator 등이 해당

p : production = 생성 규칙 // 생성규칙,production_rule?

위 단말기호들과 비단말기호들을 써서 문자열을 만들어 내는 방법을 열거한 것
보통 V → (V ∪ T) 같은 방식으로 쓰인다... ('비단말 -> 단말 or 비단말' 이라는 뜻)
모든 생성규칙에선 왼쪽(좌항)에 오는 기호는 단 하나만 쓰인다. (i.e.조건이나 상황에 상관없이 좌항은 항상 우항으로 유도가능???)

s : starting = 시작기호

한 개의 비단말기호(voca non terminal)를 정의함
이 비단말기호가 바로 시작기호이며, 이 문법의 시작은 시작기호로부터 시작(?)

1 문맥의존문법 context-sensitive_grammar
0 (귀납적가산문법? 이런단어 있음?) = 제약없는문법???

}

[edit]