Chomsky hierarchy or Chomsky-Schützenberger hierarchy
aka 촘스키_계층
여기서 그렇게 번역하지 않은 이유는 계층 하면 stratum, level, layer 같은 평평한 이미지가 있어서. 계층"들"이나 계층체계나 계층구조라면 괜찮지만. 2021-12-02
형식언어,formal_language를 생성하는 형식문법,formal_grammar을 분류해 놓은 계층구조.//from wpko and wpen; chk.
문법/언어는 위로 갈수록 더 universal?
자동기계,automaton는 위로 갈수록 더 powerful?
유형 | 문법,grammar | 언어,language | 인식 오토마톤(자동기계,automaton) | 생성규칙,production_rule | 언어의 예 | ||
제0유형 | 제약 없는 문법, 무제약 문법 | unrestricted grammar | UG | 귀납적 가산 언어 recursively enumerable language | Turing_machine | - | |
제1유형 | 문맥의존문법 | context-sensitive grammar | CSG | 문맥의존언어 context-sensitive language | 선형 구속형 비결정론적 튜링 기계 linear-bounded non-deterministic Turing machine | ||
제2유형 | 문맥자유문법 | context-free grammar | CFG | 문맥자유언어 context-free language | 비결정론적 푸시다운 오토마톤 non-deterministic pushdown automaton | ||
제3유형 | 정규문법 | regular grammar | RG | 정규언어 regular language | 유한상태기계 finite state automaton | |
자동기계,automaton는 위로 갈수록 더 powerful?
recursively_enumerable_language
// recursively enumerable language는 한국어 번역이... 일단 재귀_열거_언어에 따르면.... 도대체 pagename을 뭐로 해야할지?
문맥자유언어,context-free_language,CFL
정규언어,regular_language
// recursively enumerable language는 한국어 번역이... 일단 재귀_열거_언어에 따르면.... 도대체 pagename을 뭐로 해야할지?
재귀 열거 언어
순환 열거 언어 (에서 넘어옴)
재귀적 열거 가능 언어
귀납적 가산 언어
부분 결정성 언어
튜링 수리성 언어
문맥의존언어,context-sensitive_language,CSL순환 열거 언어 (에서 넘어옴)
재귀적 열거 가능 언어
귀납적 가산 언어
부분 결정성 언어
튜링 수리성 언어
문맥자유언어,context-free_language,CFL
정규언어,regular_language
문법,grammar column만
3 정규문법 regular_grammar
2 문맥자유문법,context-free_grammar,CFG
0 (귀납적가산문법? 이런단어 있음?) = 제약없는문법???
3 정규문법 regular_grammar
2 문맥자유문법,context-free_grammar,CFG
AKA 문맥무관문법??
4-tuple (v,t,p,s)로 정의
1 문맥의존문법 context-sensitive_grammar4-tuple (v,t,p,s)로 정의
v : voca non terminal = 비 단말기호 집합 : 유한개의 원소를 가짐
문자열 만들 때 중간과정으로 쓰임
보통 대문자로 표기?
다른 기호로 유도 가능 (유도: 규칙을 한 번 써서 변환하는 것)
언어에서 직접 쓰이는 기호보다는 그들을 포괄하는 개념들이 비단말임 (??)
t : terminal voca = 단말 기호 집합 : 유한개의 원소를 가짐보통 대문자로 표기?
다른 기호로 유도 가능 (유도: 규칙을 한 번 써서 변환하는 것)
언어에서 직접 쓰이는 기호보다는 그들을 포괄하는 개념들이 비단말임 (??)
위의 비단말기호와는 서로소(disjoint)
단말기호는 다른 기호로의 유도가 불가능 (단말이라는 의미)
언어에서 직접 쓰이는 기호,symbol : 알파벳,alphabet, 숫자,digit, 연산자,operator 등이 해당
p : production = 생성 규칙 // 생성규칙,production_rule?단말기호는 다른 기호로의 유도가 불가능 (단말이라는 의미)
언어에서 직접 쓰이는 기호,symbol : 알파벳,alphabet, 숫자,digit, 연산자,operator 등이 해당
위 단말기호들과 비단말기호들을 써서 문자열을 만들어 내는 방법을 열거한 것
보통 V → (V ∪ T) 같은 방식으로 쓰인다... ('비단말 -> 단말 or 비단말' 이라는 뜻)
모든 생성규칙에선 왼쪽(좌항)에 오는 기호는 단 하나만 쓰인다. (i.e.조건이나 상황에 상관없이 좌항은 항상 우항으로 유도가능???)
s : starting = 시작기호보통 V → (V ∪ T) 같은 방식으로 쓰인다... ('비단말 -> 단말 or 비단말' 이라는 뜻)
모든 생성규칙에선 왼쪽(좌항)에 오는 기호는 단 하나만 쓰인다. (i.e.조건이나 상황에 상관없이 좌항은 항상 우항으로 유도가능???)
한 개의 비단말기호(voca non terminal)를 정의함
이 비단말기호가 바로 시작기호이며, 이 문법의 시작은 시작기호로부터 시작(?)
이 비단말기호가 바로 시작기호이며, 이 문법의 시작은 시작기호로부터 시작(?)
0 (귀납적가산문법? 이런단어 있음?) = 제약없는문법???
}