ĐỀ TÀI BÁO CÁO MÁY TURING
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (720.2 KB, 21 trang )
Chương 7
MÁY TURING
L/O/G/O
www.trungtamtinhoc.edu.vn
Nhóm 4:
Nguyễn Thị Minh Đông
Ngô Thị Thu Hiền
Trần Thị Minh Hiếu
Trương Thị Thanh Dung
GVHD: Trần Văn Hưng
Nội dung
1. Mô tả máy turing
2. Biểu diễn máy Turing bằng biểu đồ
3. Ngôn ngữ được đoán nhận bởi máy Turing
4. Bài tập
www.trungtamtinhoc.edu.vn
Máy Turing
• Có nhiều định nghĩa về các mô hình
khác nhau của máy Turing, tuy nhiên tất
cả các mô hình này đều tương đương
với nhau. Trước hết, chúng ta sẽ xem
xét mô hình máy Turing đơn giản nhất,
được gọi là mô hình cơ bản.
www.trungtamtinhoc.edu.vn
1. Mô tả máy Turing
• Chúng ta minh họa máy Turing trong hình 7.1.
www.trungtamtinhoc.edu.vn
Máy Turing gồm:
Một bộ
điều
khiển
Một băng
Một đầu
đọc
www.trungtamtinhoc.edu.vn
Bộ điều
khiển
• Với một số hữu hạn các trạng thái, trong
đó có một trạng thái đầu và một số các
trạng thái cuối hay trạng thái thừa
nhận.
Băng
• Được chia thành ô, mỗi ô chứa một ký
hiệu
Đầu
đọc
• Đầu đọc ban đầu chỉ vào ô
chứa ký hiệu vào bên trái nhất trên băng.
www.trungtamtinhoc.edu.vn
Một bước dịch chuyển của máy Turing phụ thuộc vào
trạng thái hiện tại của bộ điều khiển và ký hiệu được
đọc trên băng mà nó thực hiện:
1. Thay đổi trạng thái. Tuy nhiên, trạng thái tiếp theo có thể là trạng
hiện tại.
2. Viết một ký hiệu lên ô đang được đọc thay thế cho ký hiệu cũ. Ký
hiệu mới được viết lên có thể là giống với ký hiệu hiện tại trên băng.
3. Dịch chuyển đầu đọc sang phải hoặc sang trái một ô.
www.trungtamtinhoc.edu.vn
Định nghĩa 7.1: Máy Turing được định
nghĩa bởi bộ bảy:
M = (Q, Σ, Γ, δ , q0, B, F)
www.trungtamtinhoc.edu.vn
trạng thái,
Trong đó:
• Σ là bảng chữ vào,
• Γ là tập các ký hiệu
sử dụng trên băng.
• S là tập con của G.
www.trungtamtinhoc.edu.vn
• B є Γ - Σ là ký hiệu trắng,
•
F Q là tập hữu hạn các trạng thái cuối/thừa
nhận.
•
là hàm dịch chuyển được định nghĩa như sau:
:Q Q
Trong đó, L và R biểu diễn “trái” hay “phải” là
hướng dịch chuyển của đầu đọc.
www.trungtamtinhoc.edu.vn
2. Biểu diễn máy Turing bằng biểu đồ
• Tương tự như ô-tô-mát hữu hạn
hay ô-tô-mát đẩy xuống, chúng
ta cũng có thể sử dụng biểu đồ
dịch chuyển biểu diễn máy
Turing mà trong đó:
www.trungtamtinhoc.edu.vn
1. Các nút biểu diễn các trạng thái.
2. Có một mũi tên đi vào nút q0 để ký
hiệu trạng thái đầu.
3. Các trạng thái kết thúc F là các nút
được biểu diễn bởi hai vòng tròn
www.trungtamtinhoc.edu.vn
•
4. Các trạng thái không thuộc F là các nút
được biểu diễn bởi chỉ một vòng tròn.
5. Các cung tương ứng với các dịch
chuyển. Một cung từ trạng thái q đến
trạng thái p được gán nhãn X / Y, D
nghĩa là: (q, X) = (p, Y, D).
www.trungtamtinhoc.edu.vn
3. Ngôn ngữ được đoán nhận bởi
máy Turing
••
Định nghĩa 7.4: Cho máy Turing
M = (Q, Σ, Γ, , q0, B, F).
Ngôn ngữ được đoán nhận bởi máy
Turing được định nghĩa:
L(M)={w}
Trong đó:
www.trungtamtinhoc.edu.vn
Định nghĩa 7.5
Ngôn ngữ được đoán nhận
bởi máy Turing được gọi là
ngôn ngữ liệt kê đệ quy.
www.trungtamtinhoc.edu.vn
4. Bài tập
•Câu 1.
a.Xây dựng máy Turing đoán nhận ngôn
ngữ {anbncn| n > 0}
M = (Q, S, G, , q0, B, F)
trong đó:
• Q = {q0, q1, q2, q3, q4},
• S = {a, b},
• G = {X, Y,T, a, b,c, B},
• F = {q4},
www.trungtamtinhoc.edu.vn
δ được xây dựng như sau:
1.δ(q0, a) = (q1, X, R).
2.δ(q1, a) = (q1, a, R).
3.δ(q1, Y) = (q1, Y, R).
4.δ(q1, b) = (q2, Y, L)
5.δ(q1, T) = (q1, T, R).
6.δ(q1, c) = (q1, T, L).
7.δ(q2, T) = (q2, R, L).
www.trungtamtinhoc.edu.vn
8. δ(q2, Y) = (q2, Y, L).
9.δ(q2, a) = (q2, a, L).
10.δ(q2, X) = (q0, X, R).
11.δ(q0, Y) = (q3, Y, R).
12.δ(q3, Y) = (q3, Y, R).
13.δ(q3, T) = (q3, T, R).
14.δ(q3, B) = (q4, B, R). Đoán nhận xâu
www.trungtamtinhoc.edu.vn
Câu 2: Xây dựng máy Turing tính hàm f(n) = n + 1, với
n là số nguyên dương.
M = ({q0, q1, q2}, {0, 1}, {0, 1, B}, δ, q0, B, {q2})
với δ được xây dựng như sau:
1.
δ(q0, 0) = (q0, 0, R). Dịch phải tìm ký hiệu cuối cùng.
2.
δ(q0, 1) = (q0, 1, R). Dịch phải tìm ký hiệu cuối cùng.
3.
δ(q0, B) = (q1, B, L). Gặp ký hiệu cuối.
4.
δ(q1, 0) = (q2, 1, L). Nếu ký hiệu cuối là 0 thì thay bởi 1 và
dịch trái
5.
δ(q1, 1) = (q1, 0, R). Nếu ký hiệu cuối là 1 thì thay bởi 0 và
kết thúc.
6.
δ(q1, B) = (q2, 1, R). Nếu gặp ký hiệu B bên trái thì thay
bởi 1 và kết thúc.
www.trungtamtinhoc.edu.vn
3. Xây dựng máy Turing tính hàm f(m, n) = n-m, nếu n ≥
m
www.trungtamtinhoc.edu.vn
Thank You!
L/O/G/O
www.trungtamtinhoc.edu.vn
