Đề kiểm tra giữa kỳ học kỳ năm học 2014 - 2015 môn OTOMAT&NNHT (Đề A15)

KHOA CÔNG NGHỆ THÔNG TIN<br /> BỘ MÔN TOÁN TIN ỨNG DỤNG<br /> <br /> KIỂM TRA GIỮA KỲ - NĂM HỌC 2014-2015<br /> MÔN HỌC OTOMAT&NNHT- Đề A153<br /> <br /> (Thời gian làm bài 45 phút)<br /> <br /> Đá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<br /> (mà không phải là chép!)<br /> Câu 1. (3 điểm). Cho văn phạm G = , với P = {SaS1, S1aS1 | bS1 | a}.<br /> 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ữ<br /> L (xếp theo độ dài tăng dần và theo thứ tự từ điển).<br /> Giải: Do G là Văn phạm CQ nên L là ngôn ngữ CQ (0.5);<br /> L = {aa, aaa, aba, aaaa, aaba …}(0.5), nếu viết đúng thứ tự < 4 từ : không cho điểm, đúng 4-5<br /> từ cho đủ điểm)<br /> b/. Viết biểu diễn hữu hạn cho ngôn ngữ L.<br /> Giải: Viết được L = {a  a |   {a, b}*}, hoặc mô tả được L là ngôn ngữ gồm các từ trên<br /> bảng chữ cái {a, b}, được bắt đầu và kết thúc bởi ký hiệu ‘a’. (đều cho 1.0)<br /> c/. Xây dựng otomat hữu hạn A sao cho T(A) = L(G).<br /> Giải: Từ văn phạm G, xây dựng otomat A như sau: A = < { S, S 1 , E}, {a, b},  , S, {E} >,<br /> trong đó hàm  xác định như sau: (S, b) =  ; (S, a) = S1 ; (S1, a) = {S1, E}, (S1, b) = S1,<br /> (E, a) = (E, b) = . (1.0)<br /> 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)<br /> <br /> Câu 2. (4 điểm). Cho otomat hữu hạn A có đồ thị chuyển như hình vẽ:<br /> a/. A là otomat loại gì ? (DFA, NFA, đầy đủ hay không đầy đủ)<br /> Giải: Suy luận trực tiếp từ các cung trên đồ thị, hoặc<br /> đưa về dạng bảng, rồi kết luận là DFA và đầy đủ (1.0).<br /> (nếu chỉ kết luận không giải thích cho 0.5)<br /> b/. Xác định ngôn ngữ L = T(A).<br /> Giải: L = { 1n0m 1  | n > 0, m > 1,   {0, 1}* }. (1.0)<br /> c/. Xây dựng văn phạm G sao cho L(G) = T(A).<br /> Giải: G = < {0, 1}; {q0, q1, q2}, q0, { q01q0 | 0q1 ; q10q1 |1q2 |1; q20q2 |1q2| 0 |1}><br /> (nếu thiếu 1 vài quy tắc vẫn cho đủ 1.0 điểm)<br /> d/. L là ngôn ngữ chính quy hay phi ngữ cảnh, tại sao?<br /> 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<br /> bởi Văn phạm CQ lập ở phàn c/. (1.0)<br /> Câu 3 . (3 điểm). Cho ngôn ngữ L = {a}+.{b}* .<br /> 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à<br /> ngôn ngữ chính quy hay phi ngữ cảnh, tại sao?<br /> Giải: - L = {a, aa, ab, aab, abb…} (sai 1 từ vấn cho đủ 0.5)<br /> - 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<br /> là chính quy. (hoặc nhận xét khác đúng đều cho 0.5)<br /> b/. Viết biểu diễn hữu hạn cho ngôn ngữ L.<br /> Giải : L = {anbm | m > 0, n > 1} (1.0)<br /> c/. Viết biểu thức chính quy biểu diễn ngôn ngữ L.<br /> Giải : r = a+ .b* (1.0)<br /> Tổng cộng 10 điểm<br /> <br /> KHOA CÔNG NGHỆ THÔNG TIN<br /> BỘ MÔN TOÁN TIN ỨNG DỤNG<br /> <br /> KIỂM TRA GIỮA KỲ - NĂM HỌC 2014-2015<br /> MÔN HỌC OTOMAT&NNHT- Đề A154<br /> <br /> (Thời gian làm bài 45 phút)<br /> <br /> Đá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<br /> (mà không phải là chép!)<br /> Câu 1. (3 điểm). Cho văn phạm G = , với P = {SbS1, S1aS1 | bS1 | b }.<br /> a/. Gọi L = L(G), L là ngôn ngữ chính quy hay phi ngữ cảnh?. Xâu  = babab có thuộc ngôn<br /> ngữ L(G) hay không, nếu có hãy viết dãy suy dẫn đầy đủ của từ  = babab trong văn phạm G.<br /> Giải: Do G là Văn phạm CQ nên L là ngôn ngữ CQ (0.5);<br /> dãy suy dẫn đầy đủ của từ : S ├ bS1├ baS1├ babS1├ babaS1├ babab (0.5)<br /> b/. Viết biểu diễn hữu hạn cho ngôn ngữ L.<br /> Giải: Viết được L = {b  b |   {a, b}*}, hoặc mô tả được L là ngôn ngữ gồm các từ trên<br /> bảng chữ cái {a, b}, được bắt đầu và kết thúc bởi ký hiệu ‘b’. (đều cho 1.0)<br /> c/. Xây dựng otomat hữu hạn A sao cho T(A) = L(G).<br /> Giải: Từ văn phạm G, xây dựng otomat A như sau: A = < { S, S1 , E}, {a, b},  , S, {E} >,<br /> trong đó hàm  xác định như sau: (S, a) =  ; (S, b) = S1 ; (S1, a) = S1 ; (S1, b) = {S1, E},<br /> (E, a) = (E, b) = . (1.0)<br /> 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)<br /> <br /> Câu 2. (4 điểm). Cho otomat hữu hạn A có đồ thị chuyển như hình vẽ:<br /> a/. A là otomat loại gì ? (DFA, NFA, đầy đủ hay không đầy đủ)<br /> Giải: Suy luận trực tiếp từ các cung trên đồ thị, hoặc<br /> đưa về dạng bảng, rồi kết luận là DFA và không đầy đủ<br /> (nếu chỉ kết luận đúng không giải thích cho 0.5)<br /> b/. Xác định ngôn ngữ L = T(A).<br /> Giải: L = { 1n01m 0 | n, m > 0, m > 1 }. (1.0)<br /> c/. Xây dựng văn phạm G sao cho L(G) = T(A).<br /> Giải: G = < {0, 1}; {q0, q1, q2}, q0, { q01q0 | 0q1 ; q11q1 | 0q2 | 0}><br /> (nếu thiếu 1 vài quy tắc vẫn cho đủ 1.0 điểm)<br /> d/. L là ngôn ngữ chính quy hay phi ngữ cảnh, tại sao?<br /> Giải: L là ngôn ngữ chính quy vì được đớn nhận bởi otomat hữu hạn (1.0) (hoặc được sinh bởi<br /> văn phạm chính quy vừa xây dựng, cũng cho 1.0))<br /> Câu 3 . (3 điểm). Cho ngôn ngữ L = {a}*.{b}+ .<br /> 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à<br /> ngôn ngữ chính quy hay phi ngữ cảnh, tại sao?<br /> Giải: - L = {b, ab, bb, aab, abb, bbb, aaab…} (sai 1-2 từ vấn cho đủ 0.5)<br /> - 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<br /> là chính quy. (hoặc nhận xét khác đúng đều cho 0.5)<br /> b/. Viết biểu diễn hữu hạn cho ngôn ngữ L.<br /> Giải : L = {anbm | n > 0, m > 1} (1.0)<br /> c/. Viết biểu thức chính quy biểu diễn ngôn ngữ L.<br /> Giải : r = a* .b+ (1.0)<br /> Tổng cộng 10 điểm<br /> <br />