유형 | 문법,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 | |