Tin học - Chương 7: Máy turing (turing machine)

Nội dung text: Tin học - Chương 7: Máy turing (turing machine)

1. Chương 7: Máy Turing (Turing Machine) Nội dung: • Mô hình TM • TM nhận dạng ngôn ngữ • TM tính toán hàm số nguyên • Các kỹ thuật xây dựng TM 1
2. Mô hình TM Định nghĩa: TM là một hệ thống gồm 7 thành phần M (Q, Σ, Γ, δ, q0, B, F) ● Q : tập hữu hạn các trạng thái ● Σ : bộ ký hiệu nhập ● Γ : tập hữu hạn các ký hiệu được viết trên băng ● δ : hàm chuyển Q x Γ → Q x Γ x {L, R, Ø} ● q0 : trạng thái khởi đầu ● B : ký hiệu dùng để chỉ khoảng trống trên băng ● F  Q : tập các trạng thái kết thúc Hình thái: α1qα2 với q là trạng thái hiện hành của TM, α1α2 là nội dung của băng tính từ đầu băng cho đến ký hiệu khác Blank bên phải nhất 2
3. Phép chuyển Định nghĩa: Đặt X1X2 Xi-1qXi Xn là một hình thái (ID) Giả sử : δ(q, Xi) = (p, Y, L) • Nếu i - 1 = n thì Xi là B • Nếu i = 1 thì không có ID kế tiếp (đầu đọc không được phép vượt qua cận trái của băng. • Nếu i > 1 ta viết: X1X2 Xi-1qXi Xn ⊢ X1X2 Xi-2pXi-1YXi+1 Xn Tương tự : δ(q, Xi) = (p, Y, R) X1X2 Xi-1qXi Xn ⊢ X1X2 Xi-2Xi-1YpXi+1 Xn Và với : δ(q, Xi) = (p, Y, Ø) X1X2 Xi-1qXi Xn ⊢ X1X2 Xi-2Xi-1pYXi+1 Xn 3
4. TM nhận dạng ngôn ngữ Định nghĩa: ngôn ngữ được chấp nhận bởi TM M là L(M) = {w | w Γ* và q0w ⊢ α1pα2 với p F} Ví dụ: thiết kế TM chấp nhận L = {0n1n | n > 0} Đặt TM M(Q, Σ, Γ, δ, q0, B, F) với Q = {q0, q1, q2, q3, q4}, Γ = {0, 1, X, Y, B}, F = {q4} q 0011 Xq 011 X0q 11 X q 0Y1 q X0Y1 X Xét chuỗi 0011 ta có: 0 ⊢ 1 ⊢ 1 ⊢ 2 ⊢ 2 ⊢ q 0Y1 XXq Y1 XXY q 1 XX q YY X q XYY XX q YY XXYq Y 0 ⊢ 1 ⊢ 1 ⊢ 2 ⊢ 2 ⊢ 0 ⊢ 3 XXYYq XXYYq ⊢ 3 ⊢ 4 4
5. TM nhận dạng ngôn ngữ start q (Y,Y,R) q (B,B,Ø) q 0 3 4 (X,X,R) (Y,Y,R) (0,X,R) (1,Y,L) q q 1 2 (0,0,R) (0,0,L) (Y,Y,R) (Y,Y,L) 5
6. TM như là máy tính hàm số nguyên Quy ước: một số nguyên trong TM được viết dưới dạng nhất phân là một chuỗi số 0, cách nhau bởi 1 số 1. 000001001000B = 5, 2, 3 Ví dụ: thiết kế TM tính toán phép trừ riêng • Nếu m < n thì m \ n = 0 • Ngược lại thì m \ n = m – n • Input: 0m10nB Output: 0m\nB Đặt TM M(Q, Σ, Γ, δ, q0, B, F) với • Q = {q0, q1, q2, q3, q4, q5, q6}, Γ = {0, 1, B}, F = {q6} 6
7. TM như là máy tính hàm số nguyên q 0010 B q 010 B0q 10 B01q 0 Xét chuỗi nhập 0010 (2-1)ta có: 0 ⊢ 1 ⊢ 1 ⊢ 2 ⊢ B0q 11 Bq 011 q B011 Bq 011 BBq 11 BB1q 1 BB11q 3 ⊢ 3 ⊢ 3 ⊢ 0 ⊢ 1 ⊢ 2 ⊢ 2 ⊢ BB1q 1 BBq 1 Bq Bq 0 4 ⊢ 4 ⊢ 4 ⊢ 6 q 0100 Bq 100 B1q 00 Bq 110 Xét chuỗi nhập 0100 (1-2) ta có: 0 ⊢ 1 ⊢ 2 ⊢ 3 ⊢ q B110 Bq 110 BBq 10 BBBq 0 BBBBq BBBBq 3 ⊢ 0 ⊢ 5 ⊢ 5 ⊢ 5 ⊢ 6 q (B,B,Ø) q 5 6 (1,B,R) (0,B,R) (B,0,Ø) (1,B,R) (0,B,R) start q q q (1,B,L) 0 1 4 (0,0,L) (B,B,R) (0,0,R) (B,B,L) (1,1,R) q q (0,0,L) 3 2 (0,1,L) (1,1,R) (1,1,L) 7
8. Kỹ thuật lưu trữ trong bộ điều khiển Ví dụ: thiết kế TM kiểm tra ký tự đầu tiên của một chuỗi không xuất hiện ở bất kỳ vị trí nào khác trong chuỗi. Xây dựng: TM M(Q, {0, 1}, {0, 1, B}, δ, [q0, B], B, F) trong đó các trạng thái thuộc Q là một cặp {q0, q1} x {0, 1, B} F = {[q1, B]} Phép chuyển: δ([q0, B], 0) = ([q1, 0], 0, R) δ([q1, 0], 0) = ([q1, 0], 0, R) δ([q1, 0], B) = ([q1, B], B, Ø) δ([q0, B], 1) = ([q1, 1], 1, R) δ([q1, 1], 1) = ([q1, 1], 1, R) δ([q1, 1], B) = ([q1, B], B, Ø) 8
9. Kỹ thuật dịch qua (Shifting over) Ví dụ: thiết kế máy Turing để dịch một chuỗi các ký hiệu khác B sang phải 2 ô Xây dựng: TM M(Q, Σ, Γ, δ, q0, B, F) trong đó Q chứa các phần tử dạng [q, A1, A2] với q = q1 hoặc q2; A1 và A2 thuộc Γ. Trạng thái bắt đầu là [q1, B, B] Phép chuyển: δ([q1, B, B], A1) = ([q1, B, A1], X, R) (X là ký hiệu đặc biệt nào đó) δ([q1, B, A1], A2) = ([q1, A1, A2], X, R) δ([q1, A1, A2], A3) = ([q1, A2, A3], A1, R) δ([q1, Ai-2, Ai-1], Ai) = ([q1, Ai-1, Ai], Ai-2, R) δ([q1, An-1, An], B) = ([q2, An, B], An-1, R) δ([q2, An, B], B) = ([q2, B, B], An, L) 9
10. Kỹ thuật chương trình con Ví dụ: thiết kế TM thực hiện phép nhân 2 số nguyên dương m và n • Input: 0m10nB • Output: 0m*nB • Ý tưởng: đặt số 1 sau 0m10n (0m10n1), sau đó chép n số 0 sang phải m lần, mỗi lần xóa đi 1 số 0 bên trái của m • Sau khi m đã được xóa, phép nhân đã được thực hiện xong, xóa tiếp 10n1. Kếu quả còn lại sẽ là B0m*nB Phân tích: • Xóa 1 số 0 bên trái của m, dịch đầu đọc sang số n để chuẩn bị m n m-1 n cho việc copy n số 0: q00 10 1 ⊢ B0 1q10 1 m-1 n m-1 n n • Copy n số 0 sang phải: B0 1q10 1 ⊢ B0 1q50 10 m-1 n n m-1 n n • Quay lại trạng thái bắt đầu: B0 1q50 10 ⊢ Bq00 10 10 • Chuẩn bị cho việc copy kế tiếp: m-1 n n 2 m-2 n n B0 1q50 10 ⊢ B 0 1q10 10 • Copy n số 0 sang phải 10
11. Kỹ thuật chương trình con Thủ tục copy n số 0: m n m-1 n Biến đổi hình thái q00 10 1 ⊢ B0 1q10 1: (q , 0) = (q , B, R) (q , 0) = (q , 0, R) (q , 1) = (q , 1, R) 0 6 6 6 6 1 i m-i n n*i i+1 m-i-1 n n*i Biến đổi hình thái B 0 1q50 10 ⊢ B 0 1q10 10 : 11
12. Kỹ thuật chương trình con start q (0,B,R) q (0,0,R) 0 6 (1,1,R) (2,2,R) q (0,2,R) q (B,0,L) q 1 2 3 (1,1,L) (0,0,R) (0,0,L) (B,B,R) (1,1,R) (1,1,L) (2,0,L) q 4 (1,1,R) q (0,0,L) q (1,1,L) q (0,0,L) q 5 7 8 9 (0,0,L) (0,B,R) (B,B,R) (1,B,Ø) (1,B,R) q12 q11 q10 12