TAILIEUCHUNG - NỘI DUNG ÔN TẬP MÔN LÝ THUYẾT AUTOMATA & NNHT DÀNH CHO CÁC LỚP CHÍNH QUI

Nội dung dự kiến Ngôn ngữ phi ngữ cảnh (NNPNC), VPPNC, NNPNC tuyến tính, VPPNC tuyến tính Dẫn xuất (DX), DX trái nhất - phải nhất, cây DX Tính nhập nhằng trong văn phạm và ngôn ngữ Các phép biến đổi văn phạm và hai dạng chuẩn Phân tích cú pháp (PTCP), độ phức tạp của các giải thuật PTCP Phương pháp vét cạn, giải thuật PTCP theo CYK Automata đẩy xuống không đơn định (NPDA) và đơn định DPDA NNPNC đơn định, các văn phạm cho NNPNC đơn định, văn phạm LL(k) Bổ đề. | NỘI DUNG ÔN TẬP MÔN LÝ THUYẾT AUTOMATA NNHT DÀNH CHO CÁC LỚP CHÍNH QUI Lưu ý Nội dung thi Chương 5 đến Chương 9 Hình thức thi Trắc nghiệm Thời gian 120 phút Số lượng câu dự kiến 50 câu Lý thuyết dự kiến 10 đến 15 câu Bài tập dự kiến 35 đến 40 câu Cho phép xem tài liệu trong 2 tờ giấy A4 Lý thuyết STT Nội dung dự kiến 1 Ngôn ngữ phi ngữ cảnh NNPNC VPPNC NNPNC tuyến tính VPPNC tuyến tính 2 Dẫn xuất DX DX trái nhất - phải nhất cây DX 3 Tính nhập nhằng trong văn phạm và ngôn ngữ 4 Các phép biến đổi văn phạm và hai dạng chuẩn 5 Phân tích cú pháp PTCP độ phức tạp của các giải thuật PTCP 6 Phương pháp vét cạn giải thuật PTCP theo CYK 7 Automata đẩy xuống không đơn định NPDA và đơn định DPDA 8 NNPNC đơn định các văn phạm cho NNPNC đơn định văn phạm LL k 9 Bổ đề bơm cho NNPNC và NNPNC tuyến tính 10 Tính đóng của họ NNPNC và các tính chất khả quyết định 11 Máy Turing 12 Mô hình phân cấp theo Chomsky Bài tập STT Bài tập dự kiến 1 Cho ngôn ngữ L tìm văn phạm G 2 Cho G tìm L 3 Nhận biết G nhập nhằng trên chuỗi nào 4 Tìm dẫn xuất của w trên G 5 Loại bỏ các loại luật sinh - vô dụng - đơn vị - trống 6 Biến đổi văn phạm thành dạng chuẩn Chomsky Greibach 7 Phân tích cú pháp bằng giải thuật CYK 8 Cho L tìm nPdA 9 Cho NPDA tìm L 10 Tìm dãy chuyển hình trạng của NPDA chấp nhận w 11 Cho G tìm NPDA 12 Cho dãy dẫn xuất của w tìm dãy chuyển hình trạng tương ứng của w 13 Cho L tìm DPDA 14 Cho DPDA tìm L 15 Tìm dãy chuyển hình trạng của DPDA chấp nhận w 16 Cho L tìm văn phạm LL k chủ yếu k 1 hoặc 2 17 Nhận biết một văn phạm có thuộc họ LL k không chủ yếu k 1 hoặc 2 18 Phân tích cú pháp cho chuỗi w trên văn phạm LL 1 19 Nhận biết một ngôn ngữ có phi ngữ cảnh hoặc phi ngữ cảnh tuyến tính hay không 20 Cho máy Turing M nhận biết ngôn ngữ L được chấp nhận bởi M MỘT SỐ BÀI TẬP ÔN ĐÁP ÁN Ghi chú Các đáp án ở đây không phải là duy nhất các bạn sinh viên có thể tìm thấy các đáp án khác. 1. Cho các ngôn ngữ L sau tìm các văn phạm G tương ứng L1 a2 1b 2 n 0 L2 w e a b na w nb w 1 L3 w e a b na w nb w 1

• Chứng chỉ quốc tế
• thủ thuật máy tính
• công nghệ thông tin
• tin học
• quản trị mạng
• computer network
• cách sử dụng máy tính
• thủ thuật hay máy tính
• bí quyết sử dụng máy tính
• thủ thuật dùng máy tính
• Thủ thuật Excel
• Định dạng văn bản
• Kinh nghiệm máy tính
• Mẹo vặt máy tính
• Thủ thuật soạn thảo văn bản
• Cách xử lý 326 lỗi máy tính
• Sửa chữa máy tính
• Thủ thuật tắt
• ngủ
• khởi động lại máy tính
• mẹo sử dụng máy tính
• khắc phục sự cố máy tính
• cách sửa lỗi máy tính
• lỗi máy tính
• cài đặt máy tính
• kỹ năng máy tính
• sửa lỗi máy tính
• kinh nghiệm cài đặt
• thủ thuật cài đặt
• hướng dẫn cài đặt
• phần mềm máy tính
• tiện ích máy tính
• kinh nghiệm sử dụng
• Thủ thuật PC
• Sử dụng máy tính hiệu quả
• Hướng dẫn sử dụng máy tính
• Thao tác máy tính thành thạo
• Thủ thuật sử dụng máy tính
• Tăng tốc máy tính
• Thủ thuật tăng tốc máy tính
• Thủ thuật cho Window XP
• Bí quyết tăng tốc máy tính
• Tuyệt chiêu tăng tốc máy tính
• mẹo khi sử dụng laptop
• lập trình máy tính
• hệ điều hành windows
• kỹ năng văn phòng
• sử dụng máy tính
• Giải pháp làm mát máy tính
• thủ thuật giải nhiệt máy tính
• Khơi thông dòng không khí
• Làm sạch máy tính
• Làm mát bằng chất lỏng giải pháp làm mát máy tính
• làm mát bằng chất lỏng
• dữ liệu máy tính
• quản trị thông tin
• hệ thống thông tin
• lập trình dữ liệu
• thuật ngữ hay
• quản trị dữ liệu
• lưu trữ dữ liệu
• Cấu trúc máy tính
• kỹ thuật máy tính
• giáo trình tin học
• kỹ thuật công nghệ
• Thủ thuật xóa
• mainboard
• kiến thức phần cứng
• phần cứng máy tính
• kỹ thuật lắp ráp
• Thủ thuật cắt BAD ổ cứng
• mẹo sửa máy tính
• khắc phục sự cố
• cách sử dụng windows
• lắp ráp máy tính
• chuyên đề máy tính
• thủ thuật Mac OS 10
• phím tắt trong window
• mẹo vặt trong window
• Windows Vista
• Windows 8
• windows 7
• Tăng tốc lướt Web
• thủ thuật yahoo
• mẹo cài hệ điều hành
• Thủ thuật sử dụng máy tính nhanh hơn ơ FPRIVATE
• mẹo cài đặt
• thủ thuật mạng