어떤 것들이 가능하고, 어떤 부분이 불가능한가?

Automata, Complexity, Computabliity

Automata theory 에서는 어떤 문제 정의, 해결에 필요한 리소스 정의?
finite automaton, context-free grammer, turing machine, 같은 것들을 다룰 예정

어떤 것들은 왜 해결 가능하고, 어떤 것들은 왜 불가능한가?

complexity theory

1. 문제의 근원을 찾아라

2. 대략적인 결과물을 쉽게 얻을 수 있는지 봐라

3. worst case 에서만 어려운 것인지도 봐라

   Finite Automaton

   formal system
   finite amount of information
   information represented by its state.
   state 는 input에 따라 변한다
   input 에 따라 state 변화, res 변화를 transaction이라고 한다.

   옳은 input을 accept라고 함. 테니스 예시 에서는 완벽하게 끝까지 가야지만 valid 라고 함
   start는 unique하지만, accept는 not unique