formal language

언어는 스트링들을 원소로 같는 집합
문법은 정의된 언어를 어떻게 표현할 지 정한다.
derivation (유도)
한 스트링에서 생성규칙 (production rule)을 적용해서 다른 스트링으로 바뀌는 것. 
sententil form(문장 형태)
스트링이 논터미널 심벌과 터미널 심벌로 구성된 것.
sentence
문장 형태 중 논터미널을 포함하지 않은 것.

문법의 분류
Noam Chomsky (촘스키) 문법.
type 0 (unrestricted grammar, ug): 생성 규칙에 아무런 제한이 없다.  α -> β 에서 α가 empty 스트링이 아니다.
type 1 (context-sensitive grammar, csg): 생성규칙 α -> β에서 β의 길이가 α 의 길이보다 길다.
type 2 (context-fre grammar, cfg): 모든 생성규칙이 A -> α의 형태이다.  A는 한개의 논터미널, α는 논터미널과 터-미널로 구성된 스트링.
type 3 (regular grammar, rg): right-linear, left-linear. right-linear는 A->tB 또는 A->t.  left-linear는 A->Bt 또는 A->t. (A,B는 논 터미널, t는 터미널.)
정규문법에 의해 생성될 수 있는 언어를 정규언어. 정규언어는 유한 오토마타에 의해서도 표현될 수 있다.
context-free 문법에 의해 생성될 수 있는 언어를 context-free언어. context-free언어는 푸시다운 오토마타에 의해서도 표현될 수 있다.