[오토마타] 유한 오토마타 (Finite Automata) (1)

Yellowtoast·2023년 2월 4일
0

오토마타

목록 보기
1/1

해당 글은 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)를 자주 사용함.

profile
Flutter App Developer

0개의 댓글