Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Mời các bạn chuẩn bị thi môn OTOMAT&NNHT tham khảo Đề kiểm tra giữa kỳ học kỳ năm học 2014 - 2015 môn OTOMAT&NNHT (Đề A15) sau đây nhằm chuẩn bị tốt nhất cho kì thi sắp tới. | KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN TOÁN TIN ỨNG DỤNG KIỂM TRA GIỮA KỲ - NĂM HỌC 2014-2015 MÔN HỌC OTOMAT&NNHT- Đề A153 (Thời gian làm bài 45 phút) Đáp án & Thang điểm: Có 10 ý nhỏ, mỗi ý cho 1 điểm, có thể chấp nhận sai sót nhỏ, hoặc nhầm lẫn (mà không phải là chép!) Câu 1. (3 điểm). Cho văn phạm G = , với P = {S aS1, S1 aS1 | bS1 | a}. a/. Gọi L = L(G), L là ngôn ngữ chính quy hay phi ngữ cảnh?. Viết 5 từ đầu tiên của ngôn ngữ L (xếp theo độ dài tăng dần và theo thứ tự từ điển). Giải: Do G là Văn phạm CQ nên L là ngôn ngữ CQ (0.5); L = {aa, aaa, aba, aaaa, aaba }(0.5), nếu viết đúng thứ tự , trong đó hàm xác định như sau: (S, b) = ; (S, a) = S1 ; (S1, a) = {S1, E}, (S1, b) = S1, (E, a) = (E, b) = . (1.0) Có thể chỉ cần cho A bằng đồ thị chuyển trạng thái (hoặc bảng chuyển trạng thái): (1.0) Câu 2. (4 điểm). Cho otomat hữu hạn A có đồ thị chuyển như hình vẽ: a/. A là otomat loại gì ? (DFA, NFA, đầy đủ hay không đầy đủ) Giải: Suy luận trực tiếp từ các cung trên đồ thị, hoặc đưa về dạng bảng, rồi kết luận là DFA và đầy đủ (1.0). (nếu chỉ kết luận không giải thích cho 0.5) b/. Xác định ngôn ngữ L = T(A). Giải: L = { 1n0m 1 | n > 0, m > 1, {0, 1}* }. (1.0) c/. Xây dựng văn phạm G sao cho L(G) = T(A). Giải: G = (nếu thiếu 1 vài quy tắc vẫn cho đủ 1.0 điểm) d/. L là ngôn ngữ chính quy hay phi ngữ cảnh, tại sao? Giải: L là ngôn ngữ chính quy vì được đoán nhận bởi otomat hữu hạn. (hoặc do L đươc sinh bởi Văn phạm CQ lập ở phàn c/. (1.0) Câu 3 . (3 điểm). Cho ngôn ngữ L = {a}+.{b}* . a/. Viết 7 từ đầu tiên của ngôn ngữ L (xếp theo độ dài tăng dần và theo thứ tự từ điển). L là ngôn ngữ chính quy hay phi ngữ cảnh, tại sao? Giải: - L = {a, aa, ab, aab, abb } (sai 1 từ vấn cho đủ 0.5) - Do {a}+ và {b}* là các ngôn ngữ CQ, L là tích ghép của 2 ngôn ngữ CQ nên cũng là chính quy. (hoặc nhận xét khác đúng đều cho 0.5) b/. Viết biểu diễn hữu hạn cho ngôn ngữ L. Giải : L = {anbm | m > 0, n > 1} (1.0) c/. Viết biểu thức chính quy biểu diễn ngôn ngữ L. Giải : r = a+
