결정론적 자동자

Deterministic automaton

컴퓨터 과학에서 결정론적 자동화는 한 상태에서 다른 상태로의 전환의 결과가 입력에 의해 결정되는 오토마타 이론의 개념이다.[1]: 41

일반적인 결정론적 자동화는 결정론적 유한자동화(DFA)로서, 각 상태 및 입력 기호의 쌍에 대해 다음 상태로의 전환이 하나뿐인 유한 상태 기계다.DFA는 정규 언어의 집합을 인식하고 다른 언어는 인식하지 않는다.[1]: 52

비결정론적 유한 자동화를 통해 결정론적 유한 자동화를 구축하는 표준 방법은 파워셋 건설이다.[1]: 44

참조

  1. ^ a b c Anderson, James A. (2006). Automata theory with modern applications. With contributions by Tom Head. Cambridge: Cambridge University Press. ISBN 0-521-61324-8. Zbl 1127.68049.