과목 구분 없음9급 국가직 공무원 컴퓨터일반 · 2015년04월18일 · 16/20
16.비결정적 유한 오토마타(non-deterministic finite automata)에 대한 설명으로 옳지 않은 것은?
1
한 상태에서 전이 시 다음 상태를 선택할 수 있다.
2
입력 심볼을 읽지 않고도 상태 전이를 할 수 있다.
3
어떤 비결정적 유한 오토마타라도 같은 언어를 인식하는 결정적 유한 오토마타(deterministic finite automata)로 변환이 가능하다.
4
모든 문맥 자유 언어(context-free language)를 인식한다.정답
해설
NFA는 정규 언어만 인식하며, 문맥 자유 언어 전체를 인식할 수는 없습니다. PDA는 문맥 자유 언어를 인식함