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

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!
Nội dung trích xuất từ tài liệu:
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_Turing1. Mô tả máy Turing.2. Ngôn ngữ chấp nhận bởi TM3. TM thực hiện hàm tính4. 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, ...