Bài giảng Ôtômát và ngôn ngữ hình thức: Chương 5 - ThS. Nguyễn Thị Thùy Linh

Chia sẻ: Chuheodethuong 09 | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

27
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Ôtômát và ngôn ngữ hình thức: Chương 5 Máy turing (turing machine) cung cấp cho người học những kiến thức như: Mô tả máy Turing; Ngôn ngữ chấp nhận bởi TM; TM thực hiện hàm tính; Chương trình con. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Ôtômát và ngôn ngữ hình thức: Chương 5 - ThS. Nguyễn Thị Thùy Linh

MÁY TURING ĐƯỢC GIỚI THIỆU BỞI ALAN TURING VÀO NĂM 1936. CHƯƠNG 5: MÁY TURING (TURING MACHINE) Tham khảo: http://vi.wikipedia.org/wiki/Alan_Turing 1. Mô tả máy Turing. 2. Ngôn ngữ chấp nhận bởi TM 3. TM thực hiện hàm tính 4. Chương trình con. 1 2 MÔ TẢ MÁY TURING (TT) MÔ TẢ MÁY TURING.  Mỗi bước chuyển của máy Turing, phụ thuộc vào ký hiệu  Một máy Turing gồm: do đầu đọc đọc được trên băng và trạng thái của bộ điều  Một bộ điều khiển hữu hạn. khiển, máy sẽ thực hiện các bước sau:  Một băng được chia thành các ô để lưu dữ liệu.  Chuyển trạng thái.  Một đầu đọc – viết, mỗi lần đọc có thể duyệt qua một ô trên băng để đọc hay viết ký hiệu.  In một ký hiệu trên băng tại ô đang duyệt (nghĩa là thay ký hiệu đọc được trên băng bằng ký hiệu nào đó). Input, Bộ nhớ, Output  Dịch chuyển đầu đọc – viết (sang trái (L), sang phải (R) a1 a2 … ai an B B B B … hoặc đứng yên ()).  Một cách hinh thức, ta định nghĩa máy Turing (TM) như sau: Bộ điều khiển 3 4 1
MÔ TẢ MÁY TURING (TT) MÔ TẢ MÁY TURING (TT)  Một hinh thái (thể hiện) của máy Turing M được cho bởi 1q2, trong  Định nghĩa: TM là một hệ thống gồm các thành phần M(, Q, đó q là trạng thái hiện hành của M; 12  * là nộ dung của băng tính , , q0, B, F), trong đó: từ đầu băng cho tới ký hiệu khác Blank bên phải nhất của băng. Giả sử  : bộ ký hiệu nhập. Q và  rời nhau: đầu đọc đang đọc ký hiệu bên trái nhất của 2 hoặc nếu 2 =  thì đầu đọc đọc Blank.  Q: tập hữu hạn các trạng thái.  Hàm chuyển: Ta định nghĩa một phép chuyển trạng thái của TM như  : tập hữu hạn các ký tự được phép viết trên băng. sau:  B: ký hiệu thuộc  dùng để chỉ khoảng trắng trên băng (Blank). Đặt X1X2…Xi-1qXi…Xnlà một thể hiện của TM.  : hàm chuyển ánh xạ: Q x   Q x  x {L, R, } ( có thể không  Giả sử (q, Xi) = (p, Y, L), trong đó: xác định với một vài đối với).  Nếu i – 1 = n thì Xi là B.  q0  Q là trạng thái bắt đầu.  Nếu i= 1 thì không có ID kế tiếp, nghĩa là đầu đọc không được  F  Q là tập các trạng thái kết thúc. phép vượt qua cận trái của băng. 5 6 MÔ TẢ MÁY TURING (TT) NỘI DUNG  Nếu i>1 ta viết: X1X2…Xi-1qXi…Xn |M X1X2…Xi-2pXi-1YXi+1…Xn 1. Mô tả máy Turing.  Tương tự (q, Xi) = (p, Y, R) thì ta viết: 2. Ngôn ngữ chấp nhận X1X2…Xi-1qXi…Xn |M X1X2…Xi-1YpXi+1…Xn bởi TM  Tương tự (q, Xi) = (p, Y,) thì ta viết: 3. TM thực hiện hàm tính X1X2…Xi-1qXi…Xn |M X1X2…Xi-1pYXi+1…Xn 4. Chương trình con.  Chú ý rằng nếu i-1 = n thì chuỗi Xi…Xn là rỗng và vế phải dài hơn vế trái, nghĩa là TM M mở rộng chuỗi ký hiệu trên băng. 7 8 2
NGÔN NGỮ CHẤP NHẬN BỞI TM GIẢI THUẬT  Ngôn ngữ được chấp nhận bởi TM: Ký hiệu L(M): tập hợp các chuỗi trong * là nguyên nhân đưa TM M đi đến trạng B1: Input : w = 0n1n thái kết thúc khi đã thực hiện việc thay thế từ bến trái các ký Output : yes , w  L hiệu trên băng của M với trạng thái bắt đầu q0. Một cách hình thức, ta định nghĩa tập hợp ngôn ngữ được chấp nhận bởi TM No, w L M(, Q, , , q0, B, F) là tập: B2 : ý tưởng chung: L(M) = {w| w  * và q0w |*M 1p2 với p  F còn 12 Khởi đầu TM chứa 0n1n bên trái nhất trên *} băng sau đó là vô hạn khoảng trống Blank.  Ví dụ 6.1: Thiết kế TM chấp nhận ngôn ngữ L = {0n1n | n  1 } TM lặp lại quá trình sau: 9 10 GIẢI THUẬT (TT)  Ta có thể hình dung mỗi trạng thái là một câu lệnh hoặc một nhóm câu lệnh trong chương trình. Trạng thái q0 là  TM thay 0 bên trái nhất bằng X rồi chuyển sang phải tới 1 trái nhất, trạng thái khởi đầu và nó làm cho ký hiệu 0 bên trái nhất TM thay 1 này bằng Y rồi dịch chuyển về bên trái cho tới khi gặp X phải nhất nó chuyển sang phải một ô (tới 0 trái nhất) rồi tiếp tục lập thay bằng X. Trạng thái q1 được dùng để tiến sang phải một chu trình mới. bỏ qua các số 0 và Y để tìm 1 bên trái nhất. Nếu M tìm  Nếu trong khi chuyển sang phải để tìm 1 mà TM gặp Blank thì TM thấy 1 nó thay bằng 1 bằng Y rồi đi vào trạng thái q2. dừng lại và không chấp nhận input. Tương tự, khi TM đã thay hết 0 Trạng thái q2 đưa M tiến sang trái cho tới X đầu tiên và bằng X và kiểm tra còn 1 trên băng thì TM cúng dừng và không chấp nhận input. đi vào trạng thái q0, dịch chuyển sang phải để tới 0 bên  TM chấp nhận input nếu như cũng không còn ký hiệu 1 nào trên trái nhất và tiếp tục một chu trình mới. Khi M tiến sang băng nữa. phải trong trạng thái q1, nếu B hoặc X được tiếp thấy  B3: Thiết kế: trước 1 thì input bị loại bỏ (không chấp nhận) vì có chứa  Đặt TM: M(, Q, , , q0, B, F) với các thành phần: nhiều ký hiệu 0 hơn 1 hoặc input không có dạng 0*1*. ={0, 1}; Q={q0, q1, q2, q3, q4}; ={0,1, X, Y, B} và F={q4} 11 12 3
 Trạng thái q0 còn có vai trò khác. Nếu trạng thái q2 tìm  Ký hiệu thấy X bên phải nhất thì ngay sau đó là Y thì các con số Trạng thái 0 1 X Y B 0 đã được xét hết, do đó ở trạng thái bắt đầu một chu q0 (q1, X, R) - - (q3, Y, R) - trình mới q0 không tìm thấy ký hiệu 0 nào để thay thành q1 (q1, 0, R) (q2, Y, L) - (q1, Y, R) - X mà chỉ gặp Y thì M đi vào trạng thái q3 duyệt qua các q2 (q2, 0, L) - (q0, X, R) (q2, Y, L) - Y để kiểm tra có hay không có ký hiệu 1 còn lại. Nếu q3 (q3, Y, R) (q4, B, ) theo ngay sau các Y là B, nghĩa là trên băng nhập không q4 - - - - - còn ký hiệu bào cả thì M sẽ đi vào q4 (trạng thái kết thúc) để chấp nhận input. Ngược lại input bị loại bỏ. B4 : Các phép chuyển hinh thái của TM M trên input 0011:  Hàm chuyển  được cho bởi bảng sau: q00011 | Xq1011 | X0q111 | Xq20Y1 | q2X0Y1 | Xq00Y1 | XXq1Y1 | XXYq11 | XXq2YY | Xq2XYY | XXq0YY | XXYq3Y | XXYYq3 | XXYYq4 13 Output: Yes 14  B5: Thiết kế thuật toán  B6: Cài đặt thuật toán  B7: Testing Demo NỘI DUNG 1. Mô tả máy Turing. 2. Ngôn ngữ chấp nhận bởi TM 3. TM thực hiện hàm tính 4. Chương trình con. 15 16 4
MÁY TURNG THỰC HIỆN HÀM TÍNH  Ngôn ngữ được chấp nhận bởi một máy Turing được gọi là MÁY TURNG THỰC HIỆN HÀM TÍNH (TT) ngôn ngữ đệ qui liệt kê. Lớp ngôn ngữ này rất rộng nó chứa ngôn ngữ phi ngữ cảnh và một số ngôn ngữ khác.  Ví dụ 6.2: Thiết kế máy Turing tính toán phép trừ riêng  Máy Turing như một máy tính hàm số nguyên: Ta định nghĩa phép trừ riêng như sau: Máy Turing cũng có thể được xem như là một máy tính của các hàm m – n nếu m  n   f(m,n) = m\n = số nguyên (đi từ tập số nguyên đến tập số nguyên). 0 nếu mn. Do vậy M phải thay lại tất cả n +1 số 1 sau thành B, và sau đó dịch trái thay trả lại một B về thành 0, Ta xây dựng TM như sau: M({0, 1}, {q0, q1,…, q6}, {0, 1, cuối cùng trên băng còn lại kết quả phép trừ là m-n số 0. B}, , q0, B, {q6}). TM sẽ bắt đầu bằng 0m10n trên băng và kết thúc với 0m\n trên băng. Các phép chuyển trạng thái được định nghĩa 19 như sau: 20 5
MÁY TURNG THỰC HIỆN HÀM TÍNH (TT) MÁY TURNG THỰC HIỆN HÀM TÍNH (TT) 5. (q2, B) = (q4, B, L) 1. (q0, 0) = (q1, B, R) (q4, 1) = (q4, B, L) M thay 0 đầu băng bởi B (q4, 0) = (q4, 0, L) 2. (q1, 0) = (q1, 0, R) (q4, B) = (q6, 0, ) (q1, 1) = (q2, 1, R) M di chuyển sang phải qua 0 tìm 1 Nếu ở trạng thái q2 sang phải tìm 0 để thay thành 1 nhưng chỉ gặp B thì ta xét trường hợp kết thúc i) ở trên: TM chuyển sang trạng thái 3. (q2, 1) = (q2, 1, R) q4 và chuyển sang trái đổi tất cả 1 thành B cho đến khi gặp 1 B bên (q2, 0) = (q3, 1, L) trái đầu tiên. B này sẽ được thay lại thành 0 rồi M đi vào trạng thái M di chhuyển sang phải vượt qua 1 đến khi gặp 0, đổi 0 thành 1. kết thúc q6 và dừng. (q3, 0) = (q3, 0, L) 6. (q0, 1) = (q5, B, R) 4. (q3, 1) = (q3, 1, L) (q5, 0) = (q5, B, R) (q3, B) = (q0, B, R) M dịch trái tới khi gặp B, trở về trạng thái q0 và bắt đầu một vòng lặp mới. (q5, 1) = (q5, B, R) (q5, B) = (q6, B, ) 21 22 MÁY TURNG THỰC HIỆN HÀM TÍNH (TT) Nếu ở trạng thái bắt đầu vòng lặp mới q0 gặp 1 thay vì gặp 0, NỘI DUNG thì khối các sô 0 bên trái đã xét hết, đây là trường hợp kết 1. Mô tả máy Turing. thúc ii) nêu trên: TM sẽ đi vào trạng thái q5, xóa phần còn lại của băng rồi đi vào trạng thái kết thúc q6 và dừng. 2. Ngôn ngữ chấp nhận bởi TM  Chẳng hạn TM tính toán phép trừ 2\1 (tức input 0010) như sau: 3. TM thực hiện hàm tính q00010 | Bq1010 | B0q110 | B01q20 | B0q311 | 4. Chương trình con. Bq3011 | q3B011 | Bq0011 | BBq111 | BB1q21 | BB11q2 | BB1q41 | BBq41 | Bq4BB | Bq60B. 23 24 6
CHƯƠNG TRÌNH CON CHƯƠNG TRÌNH CON (TT)  TM có thể đóng vai trò như một đoạn chương trình con với Phần chính của thủ tục trên là thủ tục COPY để chép n số 0 sang phải. trạng thái bắt đầu và trạng thái kết thúc để thực hiện lặp lại Thủ tục này được xác định bằng hàm chuyển sau: một công việc nào đó. 0 1 2 B  Ví dụ 6.3: Thiết kế TM tính toán hàm nhân 2 đối số f(m,n) q1 (q2, 2, R) (q4, 1, L) = mxn. q2 (q2, 0, R) (q2, 1, R) (q3, 0, L) M bắt đầu với 0m10n trên băng và kết thúc với 0mn trên q3 (q3, 0, L) (q3, 1, L) (q1, 2, R) băng được bao quanh bởi các Blank. q4 (q5, 1, R) (q4, 0, L) Ý tưởng chung là đặt thêm 1 sau 0m10n rồi chép khối n số Ở trạng thái q1 nhìn thấy 0, M đổi 0 thành 2 và đi vào trạng thái q2. Ở 0 sang phải m lần, mỗi lần xóa một con số 0 bên trái của trạng thái q2 M dịch phải tới Blank viết 0 rồi dịch trái trong trạng thái q3. 0m. Ta được kết quả cuối cùng là 10n10mn. Giờ chỉ việc xóa Khi ở trạng thái q3 mà gặp 2 M đi vào trạng thái q1 để tiếp tục lặp lại quá 10n1 ta được kết quả 0mn. 25 trình trên cho tới khi gặp 1. 26 CHƯƠNG TRÌNH CON (TT) CHƯƠNG TRÌNH CON (TT) Trạng thái q4 được dùng để biến đổi 2 thành 0 và thủ tục dừng tai q5. Để 0 1 2 B làm đầy đủ chương trình ta phải thêm các trạng thái để biến đổi ID khởi q5 (q7, 0, L) đầu q00m10n thành B0m-11q10n1. Tức là ta cần 3 qui tắc: q7 (q8, 1, L) (q0, 0) = (q6, B, R) q8 (q9, 0, L) (q10, B, R) (q6, 0) = (q6, 0, R) q9 (q9, 0, L) (q0, B, R) (q6, 1) = (q1, 1, R) q10 (q11, B, R) Sau đó, ta lại thêm các trạng thái cần thiết để biến đổi ID Bi0m-i1q50n10ni q11 (q11, B, R) (q12, B, R) thành Bi+10m-i-11q10n10ni là trạng thái bắt đầu lại COPY và kiểm tra có hay không i=m (tất cả các 0 của 0m đã bí xóa). Nếu i=m thì 10n1 bị xóa Vì input chỉ có 0m10n ta muốn có 0m10n1 trên băng ta cần thêm vào và tính toán dừng lại trạng thái q12 các hàm chuyển trạng thái như sau: 27 28 7
CHƯƠNG TRÌNH CON (TT) BÀI TẬP (q13, 0) = (q13, 0, R) 1.Thiết kế máy turing đoán nhận ngôn ngữ: (q13 ,1) = (q13, 1, R)  L={an bn cn , n  1} (q13, B) = (q14, 1, L)  L = { an b2n , n  1} (q14, 0) = (q14, 0, L) 2.Thiết kế máy turing thực hiện: (q14, 1) = (q14, 1, L)  a+b (q14, B) = (q0, B, R).  Từ hàm chuyển  ta có thể vẽ sơ đồ chuyển cho TM (sinh  5*n viên tự vẽ lấy).  n!  Ta có thể đánh số thứ tự của các trạng thái lại theo ý muốn. 29 30 8