촘스키 문법 구조에서 문법의 종류에 따라 사용되는 인식기의 연결이 틀린… | [사무자동화산업기사 필기] 17년 3회차 기출문제 상세 페이지
1[사무자동화산업기사 필기] 17년 3회차
촘스키 문법 구조에서 문법의 종류에 따라 사용되는 인식기의 연결이 틀린 것은?
1
Type 0 문법 - 오토마타
2
Type 1 문법 – 선형 제한 오토마타
3
Type 2 문법 – 푸시다운 오토마타
4
Type 3 문법 – 유한 오토마타
해설
촘스키 문법 체계(Chomsky Hierarchy)에서 각 문법 타입과 그에 대응하는 인식기의 연결 관계는 다음과 같다. Type 0 문법(제약 없는 문법)은 튜링 머신(Turing Machine)으로 인식되며, 단순히 '오토마타'라는 표현은 너무 광범위하고 부정확하다. Type 1 문법(문맥 의존 문법)은 선형 제한 오토마타(LBA), Type 2 문법(문맥 자유 문법)은 푸시다운 오토마타(PDA), Type 3 문법(정규 문법)은 유한 오토마타(DFA/NFA)와 각각 정확히 대응된다. 따라서 1번이 틀린 연결이다.
내용에 오류가 있거나 최신 법령·기준과 다른 부분이 보이면 알려주세요. 확인 후 반영하겠습니다.