이번 학기에 오토마타와 형식언어(Automata & Formal Language) 라는 강의를 수강하게 되었다.
컴퓨터공학을 복수전공 하려면 정말 많은 추가 학점을 들어야 하는데, 그 중 오토마타와 형식언어라는 수업에 흥미가 생겨 시작하게 되었다.
" 공개적으로 학습 "하고자 아이패드로 필기한 노트를 공유하고자 한다.
Chapter 1은 거의 개요 수준에 가까워 따로 필기를 하지는 않았고, Chapter 2 부터 본격적으로 유한 오토마타 (Finite Automata) 에 대해 배우기 시작해서 필기를 시작했다.
한 번에 많은 양의 필기를 업로드하는 것 보다는 조금씩 올리는게 좋아서 매 번 1~2장의 필기를 업로드 할 예정이다.
(악필은 미리 양해 바랍니다)
유한 오토마타 (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)를 자주 사용함.
