문제 #41178

Question

Chomsky 문법 중 생성 규칙에 제한이 없는 문법은?

Accepted Answer

Chomsky 문법에서 생성 규칙에 가장 제한이 없는 문법은 **Type 0**입니다. Type 0 문법은 **재귀적으로 열거 가능한 문법(Recursively Enumerable Grammar)**이라고도 불리며, 어떤 종류의 변환 규칙도 허용합니다. 다른 유형의 문법(Type 1, 2, 3)은 생성 규칙에 특정 제약을 두어 표현력을 제한하는 반면, Type 0은 이러한 제약이 없어 가장 강력한 표현력을 가집니다.

문제 1