오토마타 Chapter 9~11

교재 : An Introduction to Formal Languages and Automata 3rd Ed./ Peter Linz / Jones and Bartlett
교수 : 유석인 교수님
학기 : 2003/봄

Chapter 9. Turing Machines

Turing Machine
- M = (Q, Σ, Γ, δ, q_0, □, F)
- a^n b^n (n>=1) : 맨왼쪽 a 하나를 x로 바꾸고, 헤드를 옮겨 맨 왼쪽 b를 y로 바꾸고, 를 반복한 다음, a와 b가 모두 없으면 홀트.
- a(a+b)* : a를 읽고 홀트. 나머지 스트링이 무엇이든 상관없으므로.
- |w| is even : a든 b든 무조건 □로 바꾸면서 스테이트만 q_0 q_1 을 반복. 마지막엔 q_0인 경우만 파이널로 감.

Turing-computable
- 모든 w에 대해서 f(w)로 바꾸면서 홀트하는 어떤 TM이 존재할 때. f는 튜어링-컴퓨터블.

x+y 펑션의 TM
- x=3, y=4이면 11101111 로 표현된다고 생각.
- 오른쪽으로 가다가 0 이 나오면 1로 바꾸고 맨끝까지 가서 1을 다시 0으로 바꾸고 맨앞으로 돌아옴.

w를 ww로 바꾸는 펑션의 TM (w는 1의 연속)
- 1을 모두 x로 바꾸고 그 x들을 다시 1로 바꾸면서 동시에 맨끝에다가 1을 생성.


Chapter 10. Other Models of Turing Machines

Multitape TM 과 Standard TM 간의 equivalence
- 서로 simulate 할 수 있음을 증명함.
- M-TM 이 S-TM 을 simulate 함은 당연.
- S-TM 이 M-TM 을 simulate : 두개의 테잎을 4-track짜리 하나의 테잎으로 구현.

여러개의 TM을 쓰더라도 그 클래스는 Standard TM과 equivalent.
- 서로 simulate 할 수 있음을 증명함.
- 여러TM 이 하나의 TM을 simulate 함은 당연.
- 하나의 TM으로 여러 TM simulate : 멀티테잎 으로 증명?


Chapter 11. A Hierarchy of Formal Languages and Automata

- recursively enumerable : 그 랭귀지를 억셉트하는 TM이 존재한다.
- recursive : 그 랭귀지를 억셉트하는 TM이 존재하면서, 모든 입력에 대해서 홀트한다. 즉, 멤버쉽 알고리즘이 존재한다.
- 레귤러 < D컨텍스트프리, 리니어 < 컨텍스트프리 < 컨텍스트센서티브 < 리컬시브 < 리컬시브이뉴머블
- FSA(REG) < PDA(CF) < LBA(CS) < TM(UNRES)