tailieunhanh - 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! | 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 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 gt 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 .

• Kỹ thuật lập trình
• Bài giảng Ôtômát và ngôn ngữ hình thức
• Ngôn ngữ hình thức
• Chương trình con
• Máy Turing
• Thiết kế thuật toán
• Lí thuyết ngôn ngữ hình thức
• Lí thuyết ngôn ngữ hình thức và ôtômát
• Lí thuyết ngôn ngữ
• Ngôn ngữ chính quy
• Ôtômát hữu hạn
• Lớp ngôn ngữ chính quy
• Biểu diễn ngôn ngữ
• Phân cấp văn phạm
• Cấu tạo Ôtômát
• Xây dựng văn phạm cho ngôn ngữ
• Văn phạm phi ngữ cảnh
• Ôtômát đẩy xuống
• Ngôn ngữ phi ngữ cảnh
• Văn phạm chính quy
• Thuật toán Thampson
• Ngôn ngữ đoán nhận
• Bài giảng Ngôn ngữ hình thức
• Ngôn ngữ hình thức và ôtômát
• Văn phạm hình thức
• Phép toán trên từ
• Phép toán trên ngôn ngữ
• Lý thuyết ôtômát
• Lý thuyết tính toán
• Các tính chất của quan hệ
• Phép toán trên các tập hợp
• Các quan hệ tương đương
• kiến thức vật lý căn bản
• vật lí hạt nhân
• công suất điện
• cơ ứng dụng
• kỹ thuật điện tử
• database
• xử lý tương tác
• quản trị thông tin
• lập trình dữ liệu
• kỹ năng máy tính
• công nghệ điện tử
• vi mạch điện tử
• mạch điện ứng dụng
• đề cương vi xử lí
• tài liệu học đại học
• tài liệu ôn thi vật lý
• giáo trình kinh tế
• sách kinh tế học
• ngôn từ và otomat