Bài giảng Tin học lý thuyết - Chương 7: Máy Turing (Turing Machine)

Chương 7 trang bị cho người học những kiến thức về máy Turing (Turing Machine). Những nội dung chính trong chương này gồm: 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. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Tin học lý thuyết - Chương 7: Máy Turing (Turing Machine)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 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, Ø} ● q : trạng thái khởi đầu 0 ● 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úcHì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 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 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}Xét chuỗi 0011 ta có: q00011 ⊢ Xq1011 ⊢ X0q111 ⊢ X q20Y1 ⊢ q2X0Y1 ⊢ X q00Y1 ⊢ XXq1Y1 ⊢ XXY q11 ⊢ XX q2YY ⊢ X q2XYY ⊢ XX q0YY ⊢ XXYq3Y ⊢ XXYYq3 ⊢ XXYYq4 4 TM nhận dạng ngôn ngữstart (Y,Y,R) (B,B,Ø) q0 q3 q4 (X,X,R) (Y,Y,R) (0,X,R) (1,Y,L) q2 q1 (0,0,R) (0,0,L) (Y,Y,R) (Y,Y,L) 5 TM như là máy tính hàm số nguyênQuy ướ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, 3Ví 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 B Đặt TM M(Q, Σ, Γ, δ, q0, B, F) với • Q = {q , q , q , q , q , q , q }, Γ = {0, 1, B}, F = {q } 0 1 2 3 4 5 6 6 6 TM như là máy tính hàm số nguyênXét chuỗi nhập 0010 (2-1)ta có: q00010⊢Bq1010⊢B0q110⊢B01q20⊢B0q311⊢Bq3011⊢q3B011⊢Bq0011⊢BBq111⊢BB1q21⊢BB11q2⊢BB1q41⊢BBq41⊢Bq4⊢Bq60Xét chuỗi nhập 0100 (1-2) ta có: q00100⊢Bq1100⊢B1q200⊢Bq3110⊢q3B110⊢Bq0110⊢BBq510⊢BBBq50⊢BBBBq5⊢BBBBq6 (B,B,Ø) q5 q6 (1,B,R) (0,B,R) (B,0,Ø) (1,B,R) start (0,B,R) (1,B,L) q0 q1 q4 (0,0,L) (B,B,R) (0,0,R) (B,B,L) (1,1,R) q3 q2 (0,0,L) (0,1,L) (1,1,R) 7 (1,1,L) Kỹ thuật lưu trữ trong bộ điều khiểnVí 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 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â ...