[컴파일러]촘스키의 생성 문법 규칙

소개글

Chomsky, Noam는 문법을 생성 규칙의 형태에 따라 4종류(Type0에서 Type3까지)로 분류하였습니다. 각 문법의 종류별로 특징과 인식기를 정리하세요.

목차

없음

본문내용

Type-0 문법 : (unrestricted grammars) 은 모든 형식문법을 포함한다. 튜링기계 (Turing Machine) 로 인식가능한 모든 언어를 정확히 생성한다. 그 인식가능한 언어란 튜링기계가 멈추는 모든 string 들을 의미한다. 이 언어들은 또한 회귀열거가능 언어 (recursively enumerable languages) 로 알려져있다. 이것은 튜링기계를 항상 정지시켜서 결정가능한 (decided) recursive language 와는 다르다는 것을 주목해야 한다.
Type-1 문법 : (context-sensitive grammars) 은 context-sensitive languages를 생성한다. 이 문법은 αAβ → αγβ 형태의 규칙을 가진다 (A a nonterminal and α, β and γ strings of terminals and nonterminals), strings α 와 β 는 empty 일 수 있지만 γ 는 nonempty 이어야 한다. 만일 S 가 어떤 규칙의 우측에 나타나지 않으면 규칙 S → ε 가 허용된다. 이 문법으로 묘사되는 언어는 non-deterministic Turing machine (테이프가 입력의 길이를 constant time 으로 제한된) 으로 인식가능한 모든 언어들이다.

참고 자료

없음