언어, 문법 그리고 오토마타
단순한 문자열의 나열이 어떻게 계산 가능한 기계의 논리가 되는지, 오토마타 이론의 추상적 설계도를 파헤쳐 봅니다.
·언어는 심벌과 알파벳의 유한 집합에서 유도된 문자열들의 집합이며, 문법은 생성 규칙(Production Rules)을 통해 이러한 언어를 정의하는 수단이다.
·오토마타는 입력, 출력, 기억장소, 제어장치를 갖춘 디지털 컴퓨터의 추상적 모델로, 다음 상태의 결정 여부에 따라 결정적(Deterministic)과 비결정적(Non-deterministic)으로 구분된다.
·촘스키 계층은 문법의 제약 수준에 따라 네 단계(Type 0~3)로 나뉘며, 각 단계는 정규 언어부터 재귀 열거 언어까지 특정 오토마타와 일대일로 대응된다.
