tailieunhanh - 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á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 Chương 7: 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 Phép chuyển Định nghĩa: Đặt 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: ⊢ Tương tự : δ(q, Xi) = (p, Y, R) ⊢ Và với : δ(q, Xi) = (p, Y, Ø) ⊢ 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} 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 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} TM nhận dạng ngôn ngữ q0 q3 q1 q2 start (0,X,R) (Y,Y,R) (0,0,R) (Y,Y,R) (1,Y,L) (X,X,R) (0,0,L) (Y,Y,L) (Y,Y,R) q4 (B,B,Ø) TM như là máy tính hàm số nguyên Ví dụ: thiết kế TM tính toán phép trừ riêng Nếu m TM như là máy tính hàm | 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 Chương 7: 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 Phép chuyển Định nghĩa: Đặt 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: ⊢ Tương tự : δ(q, Xi) = (p, Y, R) ⊢ Và với : δ(q, Xi) = .
đang nạp các trang xem trước
