Xem mẫu
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, Ø}
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
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 q0 (Y,Y,R) q3 (B,B,Ø) q4
(0,X,R)
q1
(X,X,R)
(1,Y,L)
(Y,Y,R)
q2
(0,0,R)
(Y,Y,R)
(0,0,L)
(Y,Y,L)
5
...
- tailieumienphi.vn
nguon tai.lieu . vn