PL/오토마타, 컴파일러
[Automata] Turing Machine
SweetDev
2021. 12. 17. 16:48
Chapter 9의 내용이다!
automaton의 4가지 부류
- Finite-state machine : 간단~
- Pushdown automata
- Linear-bounded automata
- Turing machine: 복잡~ finite state machine인데 inverse가 true 아니다.
그 중 Turing Machine은 최고 등급의 automaton라고 볼 수 있다.
이 챕터를 배우기 위해서 그동안 오토마타를 배워왔다고 해도 과언이 아닐 만큼...
꽤 재미있으니까 위 나무위키 문서를 읽어보길 바란다 :)
Turing Machine의 정의
Turing Machine M은,
M = (Q, Σ, Γ, 𝛿, q_0, □, F) 로 정의된다.
Q: internal state의 집합
Σ: input alphabet
Γ: 'tape alphabet' 이라는 symbol의 유한한 집합
𝛿: transition function
Γ ∋ □ : 'blank'라는 special symbol
q_0 ∋ Q : initial state
F ⊆ Q : final state의 집합
TODO: '언어인식기로의 튜링'과 관련된 내용을 적고싶었지만 나중에...