해당 글은 2020년 컴퓨터학부 전공을 공부하면서 수강하였던 오토마타와 형식언어 라는 전공 수업을 바탕으로 정리하였습니다.
유한 오토마타 (Finite Automata)와 더불어 결정적 유한 인식기 (Deterministic Finite Accepter)에 대하여 먼저 알게 되었다.
DFA가 "결정적" 인 이유는 해당 오토마타가 항상 단 하나의 선택만을 취할 수 있기 때문이다.
1) input 내용을 고쳐쓰거나 저장 불가능
2) 임시 기억 장소를 가지고 있지 않는다
3) 임의의 순간에 저장되는 정보의 양이 엄격하게 한정된 상황만을 처리 가능
M =(Q, Σ,δ,q0,F)
Q: Internal State들의 유한 집합
Σ: Input Alphabet
δ: Total Function (Grammar 의 Production Rule 과 유사)
q0: Initial State
F: Final State
-> DFA 표현을 위해서는 전이 그래프 (Transition Graph)를 자주 사용함.