Bài giảng Automata và ngôn ngữ hình thức - Chương 7: Máy Turing

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ữ 
q
0 
q
3 
q
1 
q
2 
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) 
q
4 
(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 
q
0 
start q
1 
q
2 
q
4 
q
3 
q
5 
q
6 
(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: 
q00
m10n1 ⊢ B0m-11q10
n1 
• Copy n số 0 sang phải: B0m-11q10
n1 ⊢ B0m-11q50
n10n 
• Quay lại trạng thái bắt đầu: B0m-11q50
n10n ⊢ Bq00
m-110n10n 
• Chuẩn bị cho việc copy kế tiếp: 
B0m-11q50
n10n ⊢ B20m-21q10
n10n 
• 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 q00
m10n1 ⊢ B0m-11q10
n1: 
(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-i1q50
n10n*i ⊢ Bi+10m-i-11q10
n10n*i: 
12 
Kỹ thuật chương trình con 
q
0 
start q
6 
(0,B,R) (0,0,R) 
q
1 
(1,1,R) 
q
2 
q
3 
(0,2,R) 
(0,0,R) 
(1,1,R) 
(B,0,L) 
(0,0,L) 
(1,1,L) 
(2,2,R) 
q
4 
q
5 
(1,1,L) 
(2,0,L) 
(1,1,R) 
q
7 
q
8 
q
9 
(0,0,L) (1,1,L) (0,0,L) 
(0,0,L) 
q10 
(B,B,R) 
(B,B,R) 
q11 q12 
(1,B,R) (1,B,Ø) 
(0,B,R)