TRƯỜNG ĐẠI HỌC ĐỒNG THÁP
KHOA CÔNG NGHỆ THÔNG TIN
--- oOo ---

BÁO CÁO TIN HỌC LÝ THUYẾT
Tên Đề Tài:

THIẾT KẾ MÁY TURING
CHẤP NHẬN NGÔN NGỮ L(G)

GIẢNG VIÊN HƯỚNG DẪN

NHÓM SV THỰC HIỆN

NGUYỄN THỊ THÙY LINH

NGUYỄN THỊ THU THỦY
NGUYỄN THÀNH PHƯƠNG
LỚP : TIN2006

ĐỒNG THÁP 4/2010

1


MÁY TURING CHẤP NHẬN
NGÔN NGỮ L(G) = { 0n1n | n ≥ 1}
1.Giới thiệu bài toán
Khi cho một chuổi các bit 0 1 TM xét xem chuổi đã cho có thuộc
ngôn ngữ L(G) không.
2. Phương pháp giải quyết vấn đề


Ví dụ 2 :
Input: 00011111
Output: không chấp nhận
Các phép chuyển hình thái của TM M trên input 00011111:
q000011111B |--- Xq10011111B |--- X0q1011111B |--- X00q111111B |--X0q20Y1111B |--- Xq200Y1111B |--- q2X00Y1111B |--- Xq000Y1111B |--XXq10Y1111B |--- XX0q1Y1111B |--- XX0Yq11111B |--- XX0q2YY111B |--XXq20YY111B |--- Xq2X0YY111B |--- XXq00YY111B |--- XXXq1YY111B |--XXXYq1Y111B |--- XXXYYq1111B |--- XXXYq2YY11B |--- XXXq2YYY11B |--XXq2XYYY11B |--- XXXq0YYY11B |--- XXXYq3YY11B |--- XXXYYq3Y11B |--XXXYYYq311B

3


4


MÁY TURING CHẤP NHẬN
NGÔN NGỮ L(G) = { 0n12n | n ≥ 1}
1.Giới thiệu bài toán
Khi cho một chuổi các bit 0 1 TM xét xem chuổi đã cho có thuộc
ngôn ngữ L(G) không.
2. Phương pháp giải quyết vấn đề
Input: 0n12n
Output:
+ Chấp nhận
+ Không chấp nhận
Đặt TM M( Σ , Q, Γ , ∂ , q0, B, F) với các thành phần:
Σ ={0,1}; Q = {q1, q2, q3, q4, q5, q6}; Γ = {0 ,1, X, Y,Z, B} và F = {q6}
 Trạng thái q0 là trạng thái khởi đầu dùng để tìm 0 và Y
+ Nếu gặp 0 chuyển sang q1, ghi X rồi dịch phải
+ Nếu găp Y chuyển sang q4, ghi Y rồi dịch phải
 Trạng thái q1 dùng để tìm 1
+ Nếu gặp 1 chuyển sang q2 , ghi Y rồi dịch phải

Ví dụ 2 :
Input: 0011111
Output: không chấp nhận
Các phép chuyển hình thái của TM M trên input 0011111:
q00011111B |--- Xq1011111B |--- X0q111111B |--- X0Yq21111B |--X0q3YZ111B |--- Xq30YZ111B |--- q3X0YZ111B |--- Xq00YZ111B |--XXq1YZ111B |--- XXYq1Z111B |--- XXYZq1111B |--- XXYZYq211B |--XXYZq3YZ1B |--- XXYq3ZYZ1B |--- XXq3YZYZ1B |--- Xq3XYZYZ1B |--XXq0YZYZ1B |--- XXYq4ZYZ1B |--- XXYZq5YZ1B |--- XXYZYq5Z1B |--XXYZYZq51B

6


7