티스토리 뷰
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: '언어인식기로의 튜링'과 관련된 내용을 적고싶었지만 나중에...
'PL > 오토마타, 컴파일러' 카테고리의 다른 글
| [Automata] CFG와 Pumping Lemma (0) | 2021.12.17 |
|---|---|
| [Automata] Pushdown Automata (0) | 2021.12.17 |
| [Automata] Grammar Transforming 방법들 (0) | 2021.12.14 |
| [Automata] Context-free Language ( 문맥 자유 언어 ) (0) | 2021.11.27 |
| [Automata][WIP] 정규 언어의 성질, 비정규언어 판별하기 (3) | 2021.10.18 |