#noindex '''Chomsky hierarchy''' or '''Chomsky-Schützenberger hierarchy''' aka 촘스키_계층 여기서 그렇게 번역하지 않은 이유는 계층 하면 stratum, level, layer 같은 평평한 이미지가 있어서. 계층"들"이나 계층체계나 계층구조라면 괜찮지만. [[Date(2021-12-01T20:15:35)]] hierarchy( NdEn:hierarchy WtEn:hierarchy )에는 분명히 '수직적' 구조가 존재한다. [[형식언어,formal_language]]를 생성하는 [[형식문법,formal_grammar]]을 분류해 놓은 계층구조. //from planetmath [[형식문법,formal_grammar]]을 네 가지 type으로 분류하는 방법. 숫자가 작을수록 더 일반적. //from wpko and wpen; chk. ||유형 ||[[문법,grammar]] || || ||[[언어,language]] ||인식 오토마톤([[자동기계,automaton]]) ||[[생성규칙,production_rule]] ||언어의 예 || ||제0유형 ||제약 없는 문법,[[br]]무제약 문법 ||unrestricted grammar ||UG ||귀납적 가산 언어[[br]]recursively enumerable language ||Turing_machine ||$\alpha A \beta\to \beta$ ||- || ||제1유형 ||문맥의존문법 ||context-sensitive grammar ||CSG ||문맥의존언어[[br]]context-sensitive language ||선형 구속형 비결정론적 튜링 기계[[br]]linear-bounded non-deterministic Turing machine ||$\alpha A \beta \to \alpha \gamma \beta$ ||$a^nb^nc^n$ || ||제2유형 ||문맥자유문법 ||context-free grammar ||CFG ||문맥자유언어[[br]]context-free language ||비결정론적 푸시다운 오토마톤[[br]]non-deterministic pushdown automaton ||$A\to\alpha$ ||$a^nb^n$ || ||제3유형 ||정규문법 ||regular grammar ||RG ||정규언어[[br]]regular language ||유한상태기계[[br]]finite state automaton ||$A\to aB$ [[br]] $A\to a$ ||$a^n$ || 문법/언어는 위로 갈수록 더 universal? [[자동기계,automaton]]는 위로 갈수록 더 powerful? ---- [[recursively_enumerable_language]] // recursively enumerable language는 한국어 번역이... 일단 [[WpKo:재귀_열거_언어]]에 따르면.... 도대체 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 (귀납적가산문법? 이런단어 있음?) = 제약없는문법??? } = TBW = Chomsky 언어구조에서 문법의 분류 ↔ [[튜링_기계,Turing_machine]]의 분류 .... 에 대응관계. = tmp bmks ko = http://biohackers.net/wiki/ChomskyHierarchy = tmp bmks en = http://tunes.org/cliki/chomsky_20hierarchy.html ---- Twins: http://www.aistudy.com/linguistics/chomsky_hierarchy.htm [[WpKo:촘스키_위계]] [[WpEn:Chomsky_hierarchy]] [[Wiki:ChomskyHierarchy]] https://planetmath.org/chomskyhierarchy https://everything2.com/title/Chomsky+hierarchy Up: [[위계,hierarchy]] 분류할 것. [[컴파일러,compiler]] [[자동기계,automaton]], [[언어,language]], [[언어학,linguistics]] 관련인데..