교재 : 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인 경우만 파이널로 감...