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ị
cho việc copy n số 0: q00m10n1 ⊢ B0m-11q10n1
• Copy n số 0 sang phải: B0m-11q10n1 ⊢ B0m-11q50n10n
• Quay lại trạng thái bắt đầu: B0m-11q50n10n ⊢ Bq00m-110n10n
• Chuẩn bị cho việc copy kế tiếp:
B0m-11q50n10n ⊢ B20m-21q10n10n
12 trang |
Chia sẻ: nguyenlam99 | Lượt xem: 1201 | Lượt tải: 0
Bạn đang xem nội dung tài liệu Bài giảng Tin học - Chương 7: Máy turing, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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:
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
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
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}
Xét chuỗi 0011 ta có: q
0
0011 ⊢ Xq
1
011 ⊢ X0q
1
11 ⊢ X q
2
0Y1 ⊢ q
2
X0Y1 ⊢ X
q
0
0Y1 ⊢ XXq
1
Y1 ⊢ XXY q
1
1 ⊢ XX q
2
YY ⊢ X q
2
XYY ⊢ XX q
0
YY ⊢ XXYq
3
Y ⊢
XXYYq
3
⊢ XXYYq
4
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}
5
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,Ø)
6
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 < 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}
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
7
TM như là máy tính hàm số nguyên
Xét chuỗi nhập 0100 (1-2) ta có: q
0
0100 ⊢ Bq
1
100 ⊢ B1q
2
00 ⊢ Bq
3
110 ⊢
q
3
B110 ⊢ Bq
0
110 ⊢ BBq
5
10 ⊢ BBBq
5
0 ⊢ BBBBq
5
⊢ BBBBq6
Xét chuỗi nhập 0010 (2-1)ta có: q
0
0010 ⊢ B q
1
010 ⊢ B0q
1
10 ⊢ B01q
2
0 ⊢
B0q
3
11 ⊢ Bq
3
011 ⊢ q
3
B011 ⊢ Bq
0
011 ⊢ BBq
1
11 ⊢ BB1q
2
1 ⊢ BB11q
2
⊢
BB1q
4
1 ⊢ BBq
4
1 ⊢ Bq
4
⊢ Bq60
q0
start q1
q2
q4
q3
q5 q6
(0,B,R)
(1,B,R)
(0,0,R)
(1,1,R)
(1,1,R)(0,1,L)(0,0,L)
(1,1,L)
(B,B,L)(B,B,R)
(1,B,L)
(0,0,L)
(B,0,Ø)(0,B,R)
(1,B,R)
(B,B,Ø)
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, Ø)
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)
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ị
cho việc copy n số 0: q00m10n1 ⊢ B0m-11q10n1
• Copy n số 0 sang phải: B0m-11q10n1 ⊢ B0m-11q50n10n
• Quay lại trạng thái bắt đầu: B0m-11q50n10n ⊢ Bq00m-110n10n
• Chuẩn bị cho việc copy kế tiếp:
B0m-11q50n10n ⊢ B20m-21q10n10n
• Copy n số 0 sang phải ...
11
Kỹ thuật chương trình con
Thủ tục copy n số 0:
Biến đổi hình thái q00m10n1 ⊢ B0m-11q10n1:
δ(q
0
, 0) = (q
6
, B, R) δ(q
6
, 0) = (q
6
, 0, R) δ(q
6
, 1) = (q
1
, 1, R)
Biến đổi hình thái Bi0m-i1q50n10n*i ⊢ Bi+10m-i-11q10n10n*i:
12
Kỹ thuật chương trình con
q0
start q6
(0,B,R) (0,0,R)
q1
(1,1,R)
q2 q3(0,2,R)
(0,0,R)
(1,1,R)
(B,0,L)
(0,0,L)
(1,1,L)
(2,2,R)
q4
q5
(1,1,L)
(2,0,L)
(1,1,R)
q7 q8 q9(0,0,L) (1,1,L) (0,0,L)
(0,0,L)
q10
(B,B,R)
(B,B,R)
q11q12
(1,B,R)(1,B,Ø)
(0,B,R)
Các file đính kèm theo tài liệu này:
- ba_i_gia_ng_tin_ho_c_li_thuye_t_vo_huy_nh_tram_slide7_new_7902.pdf