형식 문법에서 type 1 문법을 인식하는데 사용되는 인식기는? | [사무자동화산업기사 필기] 19년 3회차 기출문제 상세 페이지
1[사무자동화산업기사 필기] 19년 3회차
형식 문법에서 type 1 문법을 인식하는데 사용되는 인식기는?
1
Finite Automata
2
Push Down Automata
3
Linear Bounded Automata
4
Turing Machine
해설
Type 1 문법(문맥 의존 문법, CSG)을 인식하는 인식기는 선형 제한 오토마타(Linear Bounded Automata, LBA)이다. Chomsky 계층구조에서 Type 0(무제한)은 Turing Machine, Type 1(CSG)은 LBA, Type 2(CFG)는 Push Down Automata, Type 3(정규문법)은 Finite Automata가 각각 대응되며, LBA는 테이프의 크기가 입력 길이에 선형적으로 제한된 Turing Machine으로서 정확히 문맥 의존 문법의 언어들을 인식할 수 있는 능력을 가진다.
내용에 오류가 있거나 최신 법령·기준과 다른 부분이 보이면 알려주세요. 확인 후 반영하겠습니다.