emzei

- overview 실제 컴퓨터가 너무 복잡하니까, 계산이론 모델로 추상화하자! 가장 단순한 모델로 시작 ~ finite automata / finite automaton * finite automata - good model but limited amount of memory * finite automata --> pushdown automata (* stack) --> turing machine (*stack, tree) ▶ Example - controlling a toll gate / an automatic door ▶ DFA : Deterministic finite automata▷ definition - set of state - rules ( transition function) - alph..

▶ purpose & motivation - Theory of computation(계산이론): computation, algorithm: definitions: limitations of computers... - 컴퓨터에 대한 한계는 어디까지일까? 계산이란?알고리즘?정의?한계? ~ 컴퓨터의 능력이 어디까지인지 파악하고자... - 계산이론은 3가지로 구분 1. 복잡도 이론 - 복잡도 ~ "난이도"2. 계산능력 이론 - 컴퓨터의 계산 가능한 한계는 어디 ~ " 풀수 있는 것과 없는 것을 구분"3. 오토마타 이론 - 컴퓨터를 추상화 - ( finite automata / CFG / Turing machines) ~ "어떤 방식으로 추상화?" "오토마타 간의 표현능력의 차이?" ▶ mathematical p..