TAILIEUCHUNG - Bài giảng Tin học lí thuyết: Chương 7 - Võ Huỳnh Trâm

Bài giảng "Tin học lí thuyết - Chương 7: Máy Turing (Turing Machine)" cung cấp cho người học các kiến thức: Mô hình TM, TM nhận dạng ngôn ngữ, TM tính toán hàm số nguyên, các kỹ thuật xây dựng TM. nội dung chi tiết. | Chương 7 Máy Turing Turing Machine Nội dung Mô hình TM TM nhận dạng ngôn ngữ TM tính toán hàm số nguyên Các kỹ thuật xây dựng TM 1 Mô hình TM Định nghĩa TM là một hệ thống gồm 7 thành phần M Q Z r ỗ q0 B F Q tập hữu hạn các trạng thái Z bộ ký hiệu nhập r tập hữu hạn các ký hiệu được viết trên băng õ hàm chuyển Q x r Q x r x L R 0 q0 trạng thái khởi đầu B ký hiệu dùng để chỉ khoảng trống trên băng F c Q tập các trạng thái kết thúc Hình thái a1qa2 với q là trạng thái hiện hành của TM 0102 là nội dung của băng tính từ đầu băng cho đến ký hiệu khác Blank bên phải nhất 2 Phép chuyên Định nghĩa Đặt là một hình thái ID Giả sử ỗ q X. p Y L Nếu i - 1 n thì Xi là B Nếu i 1 thì không có ID kế tiếp đầu đọc không được phép vượt qua cận trái của băng. Nếu i 1 ta viết -XX .X pX YK Xn 12 i-1 i n 12 i-2 i-1 i 1 n Tương tự ỗ q X. p Y R X1X2. X - X1X2. .Xi-2Xi-1 YpXi 1. .Xn Và với õ q Xi p Y 0 X1X2. .Xi-1 qX .Xn I- X1X2. .Xi-2Xi-1 pYXi 1 .Xn

• Tin học văn phòng
• Bài giảng Tin học lí thuyết
• Tin học lí thuyết
• Mô hình TM
• TM nhận dạng ngôn ngữ
• TM tính toán hàm số nguyên
• Kỹ thuật xây dựng TM
• Bổ túc toán
• Phép chứng minh quy nạp
• Đồ thị và cây
• Phép toán tập hợp
• Sự phân cấp Chomsky
• Biểu diễn ngôn ngữ
• Sự phân lớp văn phạm
• Văn phạm phi ngữ cảnh
• Giản lược văn phạm phi ngữ cảnh
• Chuẩn hóa văn phạm phi ngữ cảnh
• Tính chất của văn phạm phi ngữ cảnh
• Automata đẩy xuống
• PDA đơn định
• PDA không đơn định
• PDA chấp nhận chuỗi
• Bài giảng Máy Turing
• Bài giảng Tin học
• Toán giải tích
• Bài giảng Toán giải tích
• Nhận dạng ngôn ngữ
• Tính toán hàm số nguyên