2019년 사무자동화산업기사 4회차 60번

Question

형식 문법에서 type 1 문법을 인식하는 데 사용되는 인식기는?

Accepted Answer

Type 1 문법(문맥 의존 문법)은 입력 문자열의 길이에 비례하는 메모리를 가진 인식기가 필요합니다. Finite Automata는 메모리가 없으므로 Type 1 문법을 인식할 수 없습니다. Push Down Automata는 스택을 사용하지만, 스택의 크기는 제한이 없어 Type 1 문법을 인식하기에는 부족합니다. Linear Bounded Automata는 입력 테이프의 길이만큼만 메모리를 사용하므로 Type 1 문법을 인식하는 데 적합합니다. Turing Machine은 무한한 메모리를 가지므로 Type 1 문법을 인식할 수 있지만, Type 1 문법을 인식하는 데 꼭 필요한 것은 아닙니다.

2019년 사무자동화산업기사 4회차 60번 - 기출문제 및 해설

문제 1