·언어는 심벌과 알파벳의 유한 집합에서 유도된 문자열들의 집합이며, 문법은 생성 규칙(Production Rules)을 통해 이러한 언어를 정의하는 수단이다.

·오토마타는 입력, 출력, 기억장소, 제어장치를 갖춘 디지털 컴퓨터의 추상적 모델로, 다음 상태의 결정 여부에 따라 결정적(Deterministic)과 비결정적(Non-deterministic)으로 구분된다.

·촘스키 계층은 문법의 제약 수준에 따라 네 단계(Type 0~3)로 나뉘며, 각 단계는 정규 언어부터 재귀 열거 언어까지 특정 오토마타와 일대일로 대응된다.

언어, 문법 그리고 오토마타