Chomsky 문법 중 생성 규칙에 제한이 없는 문법은? | [사무자동화산업기사 필기] 18년 3회차 기출문제 상세 페이지

Chomsky 문법 분류에서 Type 0 문법은 생성 규칙에 제한이 없는 유일한 문법이다. Type 0는 재귀 열거 가능 언어(recursively enumerable language)를 생성하며, 좌변과 우변의 길이에 아무런 제약이 없어 가장 표현력이 높다. Type 1(문맥민감)은 좌변 길이 ≤ 우변 길이 조건, Type 2(문맥자유)는 좌변이 단일 비단말기호, Type 3(정규)은 우변이 단일 터미널 또는 터미널+비단말기호 형태로 제한되며, Type 4는 Chomsky 표준 분류에 존재하지 않는 개념이다.