context-Free 문법 : A → γ (단, A는 논터미널 기호이고, γ는 V*에 속하는 문자열
촘스키 계층구조 : 생성규칙의 형태에 가해지는 제한에 따라 미국의 영문학자 촘스키가 4종류로 나눈 형식문법
context-sensitive 문법 : γ → β (단, |γ|≤|β| γ∈V+, β∈V*)생성규칙에 |γ|≤|β|의 제한을 가하는 것으로 비위축형 (noncontracting) 문법에 속함
공문자열 : 문자열의 길이가 0인 것, ε 혹은 λ로 표시
정규문법 : A → tB A → t 또는 A → Bt A → t(단, t ∈ V *T A, B ∈ VN)
생성규칙에 따라 두 가지 종류가 있다. A → tB, A → t 와 같은 생성규칙을 갖는 것을 우선형(right-linear)문법이라 하고 A → Bt, A → t와 같은 생성규칙을 갖는 것을 좌선형(left-linear)문법이라 함.
형식문법 : 형식언어를 생성하기 위한 규칙
논터미널 : 언어에서 문자열을 생성하는 데 사용되는 중간과정의 기호로서 보통 대문자로 표시
터미널 : 정의된 언어의 알파벳이나 기호로서 영문자의 소문자나 아라비아 숫자, 연산자 기호 등이 속함
문법기호 : 터미널과 논 터미널 기호를 문법기호(grammar symbol)라 하며 보통 V(vocabulary)로 표시
튜링기계 : unrestricted 언어를 받아들이는 인식기
유도 : derivation, 한 문자열에서 생성규칙을 한 번 적용해서 다른 문자열로 바뀌는 것
